From: Guy Steele <gls@Think.COM>
Date: Tue, 2 Jul 91 14:31:49 EDT
Message-Id: <9107021831.AA11400@strident.think.com>
To: Bill.Chiles@CHILES.SLISP.CS.CMU.edu
Cc: steele@Think.COM
In-Reply-To: Bill.Chiles@CHILES.SLISP.CS.CMU.EDU's message of Wed, 26 Jun 91 16:08:28 EDT <11333.677966908@CHILES.SLISP.CS.CMU.EDU>
Subject: TeX Macros


I haven't touched those TeX macros at all, but here is a chapter
from the book that may help to illustrate their use.
--Guy
----------------------------------------------------------------
%Part{Contrl, Root = "CLM.MSS"}
%Chapter of Common Lisp Manual.  Copyright 1984, 1988, 1989 Guy L. Steele Jr.

\clearpage\def\pagestatus{ULTIMATE}

\chapter{Control Structure}
\label{CONTRL}

Common Lisp provides a variety of special structures for organizing
programs.  Some have to do with flow of control (control structures),
while others control access to variables (environment structures).
Some of these features are implemented as special forms;
others are implemented as macros, which typically expand into
complex program fragments expressed in terms of special forms
or other macros.

Function application is the primary method for construction of Lisp
programs.  Operations are written as the application of a function
to its arguments.  Usually, Lisp programs are written as a large collection
of small functions, each of which implements a simple operation.
These functions operate by calling one another, and so larger
operations are defined in terms of smaller ones.
Lisp functions may call upon themselves recursively,
either directly or indirectly.

\begin{new}
Locally defined functions (\cd{flet}, \cd{labels}) and macros (\cd{macrolet})
are quite versatile.
The new symbol macro facility allows even more syntactic flexibility.
\end{new}

While the Lisp language
is more applicative in style than statement-oriented, it
nevertheless provides many operations that produce side effects and
consequently requires constructs for controlling the sequencing of
side effects.  The construct
\cd{progn}, which is roughly equivalent to an Algol {\bf begin}-{\bf end}
block with all its semicolons, executes a number of forms sequentially,
discarding the values of all but the last.
Many Lisp control constructs
include sequencing implicitly, in which case they are said to
provide an ``implicit \cd{progn}.''
\indexterm{implicit \cd{progn}}
Other sequencing constructs include \cd{prog1} and \cd{prog2}.

For looping, Common Lisp provides the general iteration facility
\cd{do} as well as a variety
of special-purpose iteration facilities for iterating or mapping
over various data structures.

Common Lisp provides the simple one-way conditionals \cd{when} and \cd{unless},
the simple two-way conditional \cd{if}, and the more general multi-way
conditionals such as \cd{cond} and \cd{case}.  The choice of which form
to use in any particular situation is a matter of taste and
style.

Constructs for performing non-local exits with various scoping
disciplines are provided: \cd{block}, \cd{return},
\cd{return-from},
\cd{catch}, and \cd{throw}.

The multiple-value constructs provide an efficient way for a function
to return more than one value; see \cd{values}.

\section{Constants and Variables}
\label{FUNCTION-NAME-SECTION}

Because some Lisp data objects are used to represent programs,
one cannot always notate a constant data object in a program simply
by writing the notation for the object unadorned; it would be ambiguous
whether a constant object or a program fragment was intended.
The \cd{quote} special form resolves this ambiguity.

There are two kinds of variables in Common Lisp, in effect: ordinary
variables and function names.  There are some similarities between
the two kinds, and in a few cases there are similar functions for
dealing with them, for example \cd{boundp} and \cd{fboundp}.
However, for the most part the two kinds of variables are
used for very different purposes: one to name defined functions,
macros, and special forms, and the other to name data objects.

\begin{newer}
X3J13 voted in March 1989 \issue{FUNCTION-NAME} to introduce the concept
of a {\it function-name}, which may be either a symbol or a two-element list whose
first element is the symbol \cd{setf} and whose second element is a symbol.
The primary purpose of this is to allow \cd{setf} expander functions to be
CLOS generic functions with user-defined methods.
Many places in Common Lisp that used to require a symbol for a function
name are changed to allow 2-lists as well; for example, \cd{defun}
is changed so that one may write \cd{(defun (setf~foo) ...)},
and the \cd{function} special form is changed to accept any function-name.
See also \cd{fdefinition}.

By convention, any function named \cd{(setf {\it f\/})} should return its first
argument as its only value, in order to preserve the specification that
\cd{setf} returns its {\it newvalue}.  See \cd{setf}.

Implementations are free to extend the syntax of function-names to
include lists beginning with additional symbols other than \cd{setf}
or \cd{lambda}.
\end{newer}

\subsection{Reference}

The value of an ordinary variable
may be obtained simply by writing the name of the variable
as a form to be executed.  Whether this is treated as the name
of a special variable or a lexical variable is determined
by the presence or absence of an applicable \cd{special} declaration;
see chapter~\ref{DECLAR}.

The following functions and special forms allow reference to the
values of constants and variables in other ways.

\begin{defspec}
quote object

\cd{(quote {\it x})} simply returns {\it x}.
The {\it object} is not evaluated and may be any Lisp object whatsoever.
This construct allows any Lisp object to be written as a constant
value in a program.
For example:
\begin{lisp}
(setq a 43) \\
(list a (cons a 3)) \EV\ (43 (43 . 3)) \\
(list (quote a) (quote (cons a 3)) \EV\ (a (cons a 3))
\end{lisp}
Since \cd{quote} forms are so frequently useful
but somewhat cumbersome to type, a standard abbreviation is defined for them:
any form {\it f} preceded by a single quote (\cd{~'~}) character
is assumed to have \cd{(quote~~)} wrapped around it to
make \cd{(quote {\it f})}.
For example:
\begin{lisp}
(setq x '(the magic quote hack))
\end{lisp}
is normally interpreted by \cd{read} to mean
\begin{lisp}
(setq x (quote (the magic quote hack)))
\end{lisp}
See section~\ref{MACRO-CHARACTERS-SECTION}.

\begin{newer}
X3J13 voted in January 1989 \issue{CONSTANT-MODIFICATION} to clarify that
it is an error to destructively modify any object that appears as a constant
in executable code, whether within a \cd{quote} special form or as
a self-evaluating form.

See section~\ref{COMPILER-SECTION} for a discussion of how quoted constants
are treated by the compiler.
\end{newer}

\begin{newer}
X3J13 voted in March 1989 \issue{QUOTE-SEMANTICS} to clarify that
\cd{eval} and \cd{compile} are not permitted either to copy or
to coalesce (``collapse'') constants (see \cd{eq})
appearing in the code they process; the resulting
program behavior must refer to objects that are \cd{eql} to the
corresponding objects in the source code.
Moreover, the constraints introduced by the votes on
issues \issue{CONSTANT-COMPILABLE-TYPES}
and \issue{CONSTANT-CIRCULAR-COMPILATION}
on what kinds of objects may appear
as constants apply only to \cd{compile-file} (see section~\ref{COMPILER-SECTION}).
\end{newer}
\end{defspec}

\begin{defspec}
function fn

The value of \cd{function} is always the functional interpretation
of {\it fn}; {\it fn} is interpreted as if it had appeared
in the functional position of a function invocation.
In particular,
if {\it fn} is a symbol, the functional definition associated with
that symbol is returned; see \cd{symbol-function}.
If {\it fn} is a lambda-expression, then a
``lexical closure'' is returned, that is, a function that when invoked
will execute the body of the lambda-expression in such a way as to
observe the rules of lexical scoping properly.

\begin{newer}
X3J13 voted in June 1988 \issue{FUNCTION-TYPE}
to specify that the result of a \cd{function} special form is always
of type \cd{function}.  This implies that a form \cd{(function~{\it fn\/})}
may be interpreted as \cd{(the (function~{\it fn\/}))}.

It is an error to use the \cd{function} special form on a
    symbol that does not denote a function in the lexical or global environment in
    which the special form appears.  Specifically, it is an error to use the
    \cd{function} special form on a symbol that denotes a macro or special form.
    Some implementations may choose not to signal this error for
        performance reasons, but implementations are forbidden
        to extend the semantics of \cd{function} in this respect; that is, an
        implementation is not allowed to
        define the failure to signal an error to be a ``useful'' behavior.
\end{newer}

\begin{newer}
X3J13 voted in March 1989 \issue{FUNCTION-NAME} to extend \cd{function}
to accept any function-name (a symbol or a list
whose {\it car} is \cd{setf}---see section~\ref{FUNCTION-NAME-SECTION})
as well as lambda-expressions.
Thus one may write \cd{(function (setf cadr))} to refer to the \cd{setf}
expansion function for \cd{cadr}.
\end{newer}

\indexterm{closure}
For example:
\begin{lisp}
(defun adder (x) (function (lambda (y) (+ x y))))
\end{lisp}
The result of \cd{(adder 3)} is a function that will add \cd{3} to its
argument:
\begin{lisp}
(setq add3 (adder 3)) \\
(funcall add3 5) \EV\ 8
\end{lisp}
This works because \cd{function} creates a closure of
the inner lambda-expression that is able to refer to the value \cd{3}
of the variable \cd{x} even after control has returned from the
function \cd{adder}.

More generally, a lexical closure in effect retains the ability to
refer to lexically visible {\it bindings}, not just values.
Consider this code:
\begin{lisp}
(defun two-funs (x) \\
~~(list (function (lambda () x)) \\
~~~~~~~~(function (lambda (y) (setq x y))))) \\
(setq funs (two-funs 6)) \\
(funcall (car funs)) \EV\ 6 \\
(funcall (cadr funs) 43) \EV\ 43 \\
(funcall (car funs)) \EV\ 43
\end{lisp}
The function \cd{two-funs} returns a list of two functions, each of which
refers to the {\it binding} of the variable \cd{x} created on entry to
the function \cd{two-funs} when it was called with argument \cd{6}.
This binding has the value \cd{6} initially, but \cd{setq} can alter
a binding.  The lexical closure created for the first lambda-expression
does not ``snapshot'' the value \cd{6} for \cd{x} when the closure is created.
The second function can be used to alter the binding (to \cd{43}, in the
example), and this altered
value then becomes accessible to the first function.

In situations where a closure of a lambda-expression over the same set
of bindings may be produced more than once, the various resulting closures
may or may not be \cd{eq}, at the discretion of the implementation.
For example:
\begin{lisp}
(let ((x 5) (funs '())) \\*
~~(dotimes (j 10) \\*
~~~~(push \#'(lambda (z) \\*
~~~~~~~~~~~~~~(if (null z) (setq x 0) (+ x z))) \\*
~~~~~~~~~~funs)) \\*
~~funs)
\end{lisp}
The result of the above expression is a list of ten closures.
Each logically requires only the binding of \cd{x}.
It is the same binding in each case,
so the ten closures may or may not be the same identical (\cd{eq}) object.
On the other hand, the result of the expression
\begin{lisp}
(let ((funs '())) \\*
~~(dotimes (j 10) \\*
~~~~(let ((x 5)) \\*
~~~~~~(push (function (lambda (z) \\*
~~~~~~~~~~~~~~~~~~~~~~~~(if (null z) (setq x 0) (+ x z)))) \\*
~~~~~~~~~~~~funs))) \\*
~~funs)
\end{lisp}
is also a list of ten closures.
However, in this case no two of the closures may be \cd{eq}, because each
closure is over a distinct binding of \cd{x}, and these bindings can
be behaviorally distinguished because of the use of \cd{setq}.

The question of distinguishable behavior is important; the result of
the simpler expression
\begin{lisp}
(let ((funs '())) \\*
~~(dotimes (j 10) \\*
~~~~(let ((x 5)) \\*
~~~~~~(push (function (lambda (z) (+ x z))) \\*
~~~~~~~~~~~~funs))) \\*
~~funs)
\end{lisp}
is a list of ten closures that {\it may} be pairwise \cd{eq}.  Although
one might think that a different binding of \cd{x} is involved for
each closure (which is indeed the case), the bindings cannot be distinguished
because their values are identical and immutable, there being no occurrence
of \cd{setq} on \cd{x}.  A compiler would therefore be justified in
transforming the expression to
\begin{lisp}
(let ((funs '())) \\*
~~(dotimes (j 10) \\*
~~~~(push (function (lambda (z) (+ 5 z))) \\*
~~~~~~~~~~funs)) \\*
~~funs)
\end{lisp}
where clearly the closures may be the same after all.
The general rule, then, is that the implementation is free to
have two distinct evaluations of the same \cd{function} form
produce identical (\cd{eq}) closures if it can prove that the
two conceptually distinct resulting closures must in fact be
behaviorally identical with respect to invocation.
This is merely a permitted optimization; a perfectly valid
implementation might simply cause every distinct evaluation of a \cd{function}
form to produce a new closure object not \cd{eq} to any other.

Frequently a compiler can deduce that a closure in fact does not
need to close over any variable bindings.  For example,
in the code fragment
\begin{lisp}
(mapcar (function (lambda (x) (+ x 2))) y)
\end{lisp}
the function \cd{(lambda (x) (+ x 2))} contains no references to any outside
entity.  In this important special case, the same ``closure'' may be used
as the value for all evaluations of the \cd{function} special form.
Indeed, this value need not be a closure object at all; it may
be a simple compiled function containing no environment information.
This example is simply a special case of the foregoing discussion and
is included as a hint to implementors familiar with previous methods
of implementing Lisp.  The distinction between closures and other
kinds of functions is somewhat pointless, actually, as Common Lisp defines
no particular representation for closures and no way to distinguish
between closures and non-closure functions.  All that matters is that
the rules of lexical scoping be obeyed.

Since \cd{function} forms are so frequently useful
but somewhat cumbersome to type, a standard abbreviation is defined for them:
any form {\it f} preceded by \cd{\#'} (\cd{\#} followed by an apostrophe)
is assumed to have \cd{(function  )} wrapped around it to make
\cd{(function {\it f})}.  For example,
\begin{lisp}
(remove-if \#'numberp '(1 a b 3))
\end{lisp}
is normally interpreted by \cd{read} to mean
\begin{lisp}
(remove-if (function numberp) '(1 a b 3))
\end{lisp}
See section~\ref{SHARP-SIGN-MACRO-CHARACTER-SECTION}.
\end{defspec}

\begin{defun}[Function]
symbol-value symbol

\cd{symbol-value} returns the current value of the dynamic (special) variable
named by {\it symbol}.
An error occurs if the symbol has no value; see \cd{boundp}
and \cd{makunbound}.
Note that constant symbols are really variables that cannot be changed,
and so \cd{symbol-value} may be used to get the value of
a named constant.  In particular, \cd{symbol-value} of a keyword
will return that keyword.

\cd{symbol-value} cannot access the value of a lexical variable.

This function is particularly useful for implementing interpreters
for languages embedded in Lisp.
The corresponding assignment primitive is \cd{set};
alternatively, \cd{symbol-value} may be used with \cd{setf}.
\end{defun}

\begin{defun}[Function]
symbol-function symbol

\cd{symbol-function} returns the current global function definition
named by {\it symbol}.  An error is signalled if the symbol has no function
definition; see \cd{fboundp}.  Note that the definition may be a
function or may be an object representing a special form or macro.
In the latter case, however, it is an error
to attempt to invoke the object as a function.
If it is desired to process macros, special forms, and functions
equally well, as when writing an interpreter,
it is best first to test the symbol with \cd{macro-function}
and \cd{special-form-p}
and then to invoke the functional value only if these
two tests both yield false.

This function is particularly useful for implementing interpreters
for languages embedded in Lisp.

\cd{symbol-function} cannot access the value of a lexical function name
produced by \cd{flet} or \cd{labels}; it can access only
the global function value.

The global function definition of a symbol may be altered
by using \cd{setf} with \cd{symbol-function}.
Performing this operation causes the symbol to have {\it only} the
specified definition as its global function definition; any previous
definition, whether as a macro or as a function, is lost.
It is an error to attempt to redefine the name of a special
form (see table~\ref{SPECIAL-FORM-TABLE}).
\begin{newer}
X3J13 voted in June 1988 \issue{FUNCTION-TYPE} to clarify the behavior
of \cd{symbol-function} in the light of the redefinition of the type \cd{function}.
\begin{itemize}
\item It is permissible to call \cd{symbol-function}
    on any symbol for which \cd{fboundp} returns true.
 Note that \cd{fboundp} must return true for a symbol naming a macro or
    a special form.

\item If \cd{fboundp} returns true for a symbol
        but the symbol denotes a macro or special form,
        then the value returned by \cd{symbol-function} is not well-defined
        but \cd{symbol-function} will not signal an error. 

\item When \cd{symbol-function} is used with \cd{setf}
 the new value must be of type \cd{function}.
	It is an error to set the \cd{symbol-function} of a symbol to a
	symbol, a list, or the value returned by \cd{symbol-function} on
	the name of a macro or a special form.
\end{itemize}
\end{newer}
\end{defun}

\begin{newer}
\begin{defun}[Function]
fdefinition function-name

X3J13 voted in March 1989 \issue{FUNCTION-NAME} to add the function
\cd{fdefinition} to the language.
It is exactly like \cd{symbol-function}
except that its argument may be any function-name (a symbol or a list
whose {\it car} is \cd{setf}---see section~\ref{FUNCTION-NAME-SECTION});
it returns the current global function
definition named by the argument {\it function-name}.
One may use \cd{fdefinition} with \cd{setf}
to change the current global function definition associated with
a function-name.
\end{defun}
\end{newer}

\begin{defun}[Function]
boundp symbol

\cd{boundp} is true if the dynamic (special) variable named by {\it symbol}
has a value; otherwise, it returns {\false}.

See also \cd{set} and \cd{makunbound}.
\end{defun}

\begin{defun}[Function]
fboundp symbol

\cd{fboundp} is true if the symbol has a global function definition.
Note that \cd{fboundp} is true when the symbol names a special form or
macro.  \cd{macro-function} and \cd{special-form-p} may be used to test
for these cases.

\begin{newer}
X3J13 voted in June 1988 \issue{FUNCTION-TYPE} to emphasize that,
despite the tightening of the definition of the type \cd{function},
\cd{fboundp} must return true when the argument names a special form or
macro.
\end{newer}

See also \cd{symbol-function} and \cd{fmakunbound}.

\begin{newer}
X3J13 voted in March 1989 \issue{FUNCTION-NAME} to extend \cd{fboundp}
to accept any function-name (a symbol or a list
whose {\it car} is \cd{setf}---see section~\ref{FUNCTION-NAME-SECTION}).
Thus one may write \cd{(fboundp '(setf cadr))} to determine whether a \cd{setf}
expansion function has been globally defined for \cd{cadr}.
\end{newer}

\end{defun}

\begin{defun}[Function]
special-form-p symbol

The function \cd{special-form-p} takes a symbol.  If the symbol
globally names a special form,
then a non-{\false} value is returned; otherwise {\false} is returned.
A returned non-{\nil} value is typically a function
of implementation-dependent nature that can be used to
interpret (evaluate) the special form.

It is possible for {\it both} \cd{special-form-p} and \cd{macro-function}
to be true of a symbol.  This is possible because an implementation is
permitted to implement any macro also as a special form for speed.
On the other hand, the macro definition must be available
for use by programs that understand only the standard special forms
listed in table~\ref{SPECIAL-FORM-TABLE}.
\end{defun}

\subsection{Assignment}

The following facilities allow the value of a variable (more specifically,
the value associated with the current binding of the variable) to be altered.
Such alteration is different from establishing a new binding.
Constructs for establishing new bindings of variables are described
in section~\ref{VAR-BINDING-SECTION}.

\begin{defspec}
setq {var form}*

The special form \cd{(setq {\it var1} {\it form1} {\it var2} {\it form2} ...)} is the
``simple variable assignment statement'' of Lisp.
First {\it form1} is evaluated
and the result is stored in the variable {\it var1}, then {\it form2}
is evaluated and the result stored in {\it var2}, and so forth.
The variables are represented as symbols, of course, and are interpreted
as referring to static or dynamic instances according to the usual rules.
Therefore \cd{setq} may be used for assignment of both lexical
and special variables.

\cd{setq} returns the last value assigned, that is, the result of the
evaluation of its last argument.
As a boundary case, the form \cd{(setq)} is legal and returns {\false}.
There must be an even number of argument forms.
For example, in
\begin{lisp}
(setq x (+ 3 2 1) y (cons x nil))
\end{lisp}
\cd{x} is set to \cd{6}, \cd{y} is set to \cd{(6)}, and the \cd{setq}
returns \cd{(6)}.  Note that the first assignment is performed before
the second form is evaluated, allowing that form to
use the new value of \cd{x}.

See also the description of \cd{setf},
the Common Lisp ``general assignment statement'' that is capable of assigning
to variables, array elements, and other locations.

\begin{newer}
Some programmers choose to avoid
\cd{setq} as a matter of style, always using \cd{setf} for any kind of
structure modification.  Others use \cd{setq} with simple variable names and
\cd{setf} with all other generalized variables.
\end{newer}

\begin{new}
X3J13 voted in March 1989
\issue{SYMBOL-MACROLET-SEMANTICS} to specify that if any {\it var}
refers not to an ordinary variable but to a binding made by
\cd{symbol-macrolet}, then that {\it var} is handled as
if \cd{setf} had been used instead of \cd{setq}.
\end{new}
\end{defspec}

\begin{defmac}
psetq {var form}*

A \cd{psetq} form is just like a \cd{setq} form, except
that the assignments happen in parallel.  First all of the forms
are evaluated, and then the variables are set to the resulting
values.  The value of the \cd{psetq} form is {\false}.
For example:
\begin{lisp}
(setq a 1) \\
(setq b 2) \\
(psetq a b  b a) \\
a \EV\ 2 \\
b \EV\ 1
\end{lisp}
In this example, the values of \cd{a} and \cd{b} are exchanged by
using parallel assignment.
(If several variables are to be assigned in parallel in
the context of a loop, the \cd{do} construct may be appropriate.)

See also the description of \cd{psetf},
the Common Lisp ``general parallel assignment statement'' that
is capable of assigning
to variables, array elements, and other locations.

\begin{newer}
X3J13 voted in March 1989
\issue{SYMBOL-MACROLET-SEMANTICS} to specify that if any {\it var}
refers not to an ordinary variable but to a binding made by
\cd{symbol-macrolet}, then that {\it var} is handled as
if \cd{psetf} had been used instead of \cd{psetq}.
\end{newer}
\end{defmac}

\begin{defun}[Function]
set symbol value

\cd{set} allows alteration of the value of a dynamic (special) variable.
\cd{set} causes the dynamic variable named by {\it symbol} to take on
{\it value} as its value.

\begin{new}
X3J13 voted in January 1989
\issue{ARGUMENTS-UNDERSPECIFIED}
to clarify that the {\it value}
may be any Lisp datum whatsoever.
\end{new}

Only the value of the current dynamic binding is altered;
if there are no bindings in effect, the most global value is altered.
For example,
\begin{lisp}
(set (if (eq a b) 'c 'd) 'foo)
\end{lisp}
will either set \cd{c} to \cd{foo} or set \cd{d} to \cd{foo}, depending
on the outcome of the test \cd{(eq~a~b)}.

\cd{set} returns {\it value} as its result.

\cd{set} cannot alter
the value of a local (lexically bound) variable.
The special form \cd{setq}
is usually used for altering the values of variables
(lexical or dynamic) in programs.
\cd{set} is particularly useful for implementing interpreters for
languages embedded in Lisp.
See also \cd{progv}, a construct that performs binding rather
than assignment of dynamic variables.
\end{defun}

\begin{defun}[Function]
makunbound symbol \\
fmakunbound symbol

\cd{makunbound} causes the dynamic (special) variable named
by {\it symbol} to become unbound (have no value).  \cd{fmakunbound}
does the analogous thing for the global function definition named
by {\it symbol}.
For example:
\begin{lisp}
(setq a 1) \\
a \EV\ 1 \\
(makunbound 'a) \\
a \EV\ {\rm causes an error} \\
\\
(defun foo (x) (+ x 1)) \\
(foo 4) \EV\ 5 \\
(fmakunbound 'foo) \\
(foo 4) \EV\ {\rm causes an error}
\end{lisp}
Both functions return {\it symbol} as the result value.

\begin{newer}
X3J13 voted in March 1989 \issue{FUNCTION-NAME} to extend \cd{fmakunbound}
to accept any function-name (a symbol or a list
whose {\it car} is \cd{setf}---see section~\ref{FUNCTION-NAME-SECTION}).
Thus one may write \cd{(fmakunbound '(setf cadr))} to remove any
global definition of a \cd{setf} expansion function for \cd{cadr}.
\end{newer}
\end{defun}

\section{Generalized Variables}
\label{SETF-SECTION}

In Lisp, a variable can remember one piece of data,
that is, one Lisp object.
The main operations on a variable are to recover that object and
to alter the variable to remember a new object; these operations are
often called {\it access} and {\it update} operations.  The concept of
variables named by symbols can be generalized to any storage location
that can remember one piece of data, no matter how that location is
named.  Examples of such storage locations are the {\it car} and {\it cdr} of
a cons, elements of an array, and components of a structure.

For each kind of generalized variable, typically there are two functions
that implement the conceptual {\it access} and {\it update} operations.
For a variable, merely mentioning the name of the variable accesses it,
while the \cd{setq} special form can be used to update it.
The function \cd{car} accesses the {\it car} of a cons,
and the function \cd{rplaca} updates it.
The function \cd{symbol-value} accesses the dynamic value of a variable
named by a given symbol, and the function \cd{set} updates it.

Rather than thinking about two distinct functions that respectively
access and update a storage location somehow deduced from their
arguments, we can instead simply think of a call to the access function
with given arguments as a {\it name} for the storage location.  Thus, just
as \cd{x} may be considered a name for a storage location (a variable), so
\cd{(car x)} is a name for the {\it car} of some cons (which is in turn
named by \cd{x}).  Now, rather than having to remember two functions for
each kind of generalized variable (having to remember, for example, that
\cd{rplaca} corresponds to \cd{car}), we adopt a uniform syntax for updating
storage locations named in this way, using the \cd{setf} macro.
This is analogous to the way we use the \cd{setq} special form to convert
the name of a variable (which is also a form that accesses it) into a
form that updates it.  The uniformity of this approach is illustrated in
the following table.

\begin{flushleft}
\begin{tabular*}{\textwidth}{@{}l@{\extracolsep{\fill}}ll@{}}
{\rm Access Function}&{\rm Update Function}&{\rm Update Using \cd{setf}} \\
\hlinesp
\cd{x}&\cd{(setq x datum)}&\cd{(setf x datum)} \\
\cd{(car x)}&\cd{(rplaca x datum)}&\cd{(setf (car x) datum)} \\
\cd{(symbol-value x)}&\cd{(set x datum)}&\cd{(setf (symbol-value x) datum)} \\
\hline
\end{tabular*}
\end{flushleft}
\cd{setf} is actually a macro that examines an access form and
produces a call to the corresponding update function.

Given the existence of \cd{setf} in Common Lisp, it is not necessary to have
\cd{setq}, \cd{rplaca}, and \cd{set}; they are redundant.  They
are retained in Common Lisp because of their historical importance in Lisp.
However, most other update functions (such as \cd{putprop}, the update
function for \cd{get}) have been eliminated from Common Lisp
in the expectation that \cd{setf} will be uniformly used in their place.

\begin{defmac}
setf {place newvalue}*

\cd{(setf {\it place} {\it newvalue})} takes a form {\it place} that when evaluated
{\it accesses} a data object in some location and ``inverts''
it to produce a corresponding form to {\it update} the location.
A call to the \cd{setf} macro therefore
expands into an update form that stores the result of evaluating
the form {\it newvalue} into the place referred to by the access form.

If more than one {\it place}-{\it newvalue} pair is specified,
the pairs are processed sequentially; that is,
\begin{lisp}
(setf {\it place1} {\it newvalue1} \\
~~~~~~{\it place2} {\it newvalue2}) \\
~~~~~~... \\
~~~~~~{\it placen} {\it newvaluen})
\end{lisp}
is precisely equivalent to
\begin{lisp}
(progn (setf {\it place1} {\it newvalue1}) \\
~~~~~~~(setf {\it place2} {\it newvalue2}) \\
~~~~~~~... \\
~~~~~~~(setf {\it placen} {\it newvaluen}))
\end{lisp}
For consistency, it is legal to write \cd{(setf)}, which simply returns {\nil}.

The form {\it place} may be any one of the following:
\begin{itemize}
\item
The name of a variable (either lexical or dynamic).

\item
A function call form whose first element is the name of
any one of the following functions:

\begin{flushleft}
\begin{tabular}{@{}llll@{}}
\cd{aref}&\cd{car}&\cd{svref}& \\
\cd{nth}&\cd{cdr}&\cd{get}& \\
\cd{elt}&\cd{caar}&\cd{getf}&\cd{symbol-value} \\
\cd{rest}&\cd{cadr}&\cd{gethash}&\cd{symbol-function} \\
\cd{first}&\cd{cdar}&\cd{documentation~~~~~}&\cd{symbol-plist} \\
\cd{second}&\cd{cddr}&\cd{fill-pointer}&\cd{macro-function} \\
\cd{third}&\cd{caaar}&\cd{caaaar}&\cd{cdaaar} \\
\cd{fourth}&\cd{caadr}&\cd{caaadr}&\cd{cdaadr} \\
\cd{fifth}&\cd{cadar}&\cd{caadar}&\cd{cdadar} \\
\cd{sixth}&\cd{caddr}&\cd{caaddr}&\cd{cdaddr} \\
\cd{seventh~~~~~}&\cd{cdaar~~~~~}&\cd{cadaar}&\cd{cddaar} \\
\cd{eighth}&\cd{cdadr}&\cd{cadadr}&\cd{cddadr} \\
\cd{ninth}&\cd{cddar}&\cd{caddar}&\cd{cdddar} \\
\cd{tenth}&\cd{cdddr}&\cd{cadddr}&\cd{cddddr}
\end{tabular}
\end{flushleft}

\begin{new}
X3J13 voted in March 1988 \issue{AREF-1D}
to add \cd{row-major-aref} to this list.
\end{new}

%??? \begin{newer}
%X3J13 voted in June 1988 \issue{COMMON-LISP-OBJECT-SYSTEM}
%to add \cd{class-name} to this list.
%\end{newer}

\begin{newer}
X3J13 voted in June 1989 \issue{DEFINE-COMPILER-MACRO}
to add \cd{compiler-macro-function} to this list.
\end{newer}

%??? \begin{newer}
%X3J13 voted in June 1989 \issue{READ-CASE-SENSITIVITY}
%to add \cd{readtable-case} to this list.
%\end{newer}

%??? \begin{newer}
%X3J13 voted in June 1989 \issue{PATHNAME-LOGICAL}
%to add \cd{logical-pathname-translations} to this list.
%\end{newer}

\begin{newer}
X3J13 voted in March 1989 \issue{FUNCTION-NAME} to clarify that this
rule applies only when the function name refers to a global function
definition and not to a locally defined function or macro.
\end{newer}

\item
A function call form whose first element is the name of
a selector function constructed by \cd{defstruct}.

\begin{newer}
X3J13 voted in March 1989 \issue{FUNCTION-NAME} to clarify that this
rule applies only when the function name refers to a global function
definition and not to a locally defined function or macro.
\end{newer}

\item
A function call form whose first element is the name of
any one of the following functions, provided that the new value
\vadjust{\penalty-10000}%manual
is of the specified type so that it can be used to
replace the specified ``location'' (which is in each of these cases
not truly a generalized variable):

\begin{obsolete}
\begin{flushleft}
\leavevmode
\begin{tabular}{@{}ll@{}}
Function Name&Required Type \\
\hlinesp
\cd{char}&\cd{string-char} \\
\cd{schar}&\cd{string-char} \\
\cd{bit}&\cd{bit} \\
\cd{sbit}&\cd{bit} \\
\cd{subseq}&\cd{sequence} \\
\hline
\end{tabular}
\end{flushleft}
\end{obsolete}

\begin{newer}
X3J13 voted in March 1989 \issue{CHARACTER-PROPOSAL}
to eliminate the type \cd{string-char} and to redefine
\cd{string} to be the union of one or more specialized vector
types, the types of whose elements are subtypes of the type \cd{character}.
In the preceding table, the type \cd{string-char} should be replaced
by some such phrase as ``the element-type of the argument vector.''
\end{newer}

\begin{newer}
X3J13 voted in March 1989 \issue{FUNCTION-NAME} to clarify that this
rule applies only when the function name refers to a global function
definition and not to a locally defined function or macro.
\end{newer}

In the case of \cd{subseq}, the replacement value must be a sequence
whose elements may be contained by the sequence argument to \cd{subseq}.
(Note that this is not so stringent as to require that the
replacement value be a sequence of the same type as the sequence
of which the subsequence is specified.)
If the length of the replacement value does not equal the length of
the subsequence to be replaced, then the shorter length determines
the number of elements to be stored, as for the function \cd{replace}.

\item
A function call form whose first element is the name of
any one of the following functions, provided that the specified argument
to that function is in turn a {\it place} form;
in this case the new {\it place} has stored back into it the
result of applying the specified ``update'' function
(which is in each of these cases not a true update function):

\begin{flushleft}
\begin{tabular}{@{}lll@{}}
Function Name&Argument That Is a {\it place}&Update Function Used \\
\hlinesp
\cd{char-bit}&first&\cd{set-char-bit} \\
\cd{ldb}&second&\cd{dpb} \\
\cd{mask-field}&second&\cd{deposit-field} \\
\hline
\end{tabular}
\end{flushleft}

\begin{newer}
X3J13 voted in March 1989 \issue{CHARACTER-PROPOSAL}
to eliminate \cd{char-bit} and \cd{set-char-bit}.
\end{newer}

\begin{newer}
X3J13 voted in March 1989 \issue{FUNCTION-NAME} to clarify that this
rule applies only when the function name refers to a global function
definition and not to a locally defined function or macro.
\end{newer}

\item
A \cd{the} type declaration form, in which case the declaration is
transferred to the {\it newvalue} form, and the resulting \cd{setf} form is
analyzed.  For example,
\begin{lisp}
(setf (the integer (cadr x)) (+ y 3))
\end{lisp}
is processed as if it were
\begin{lisp}
(setf (cadr x) (the integer (+ y 3)))
\end{lisp}

\item
A call to \cd{apply} where the first argument form is of the form
\cd{\#'{\it name}}, that is, \cd{(function {\it name})}, where {\it name}
is the name of a function, calls to which are recognized as places by \cd{setf}.
Suppose that the use of \cd{setf} with \cd{apply} looks like this:
\begin{lisp}
(setf (apply \#'{\it name} {\it x1} {\it x2} ... {\it xn} {\it rest}) {\it x0})
\end{lisp}
The \cd{setf} method for the function {\it name} must be such that
\begin{lisp}
(setf ({\it name} {\it z1} {\it z2} ... {\it zm}) {\it z0})
\end{lisp}
expands into a store form
\begin{lisp}
({\it storefn} {\it zi${}_1$} {\it zi${}_2$} ... {\it zi${}_k$} {\it zm})
\end{lisp}
That is, it must expand into a function call such that all arguments but
the last may be any permutation or subset of the new value {\it z0} and
the arguments of the access form, but the {\it last} argument of the storing
call must be the same as the last argument of the access call.
See \cd{define-setf-method} for more details on accessing
and storing forms.

Given this, the \cd{setf}-of-\cd{apply} form shown above expands into
\begin{lisp}
(apply \#'{\it storefn} {\it xi${}_1$} {\it xi${}_2$} ... {\it xi${}_k$} {\it rest})
\end{lisp}
As an example, suppose that the variable \cd{indexes} contains a list
of subscripts for a multidimensional array {\it foo} whose rank is not
known until run time.  One may access the indicated
element of the array by writing
\begin{lisp}
(apply \#'aref foo indexes)
\end{lisp}
and one may alter the value of the indicated element to that
of \cd{newvalue} by writing
\begin{lisp}
(setf (apply \#'aref foo indexes) newvalue)
\end{lisp}

\begin{newer}
X3J13 voted in March 1989 \issue{FUNCTION-NAME} to clarify that this
rule applies only when the function name \cd{apply} refers to the global function
definition and not to a locally defined function or macro named \cd{apply}.
\end{newer}

\item
A macro call, in which case \cd{setf} expands the macro call and
then analyzes the resulting form.

\begin{newer}
X3J13 voted in March 1989 \issue{FUNCTION-NAME} to clarify that this
step uses \cd{macroexpand-1}, not \cd{macroexpand}.  This allows the chance
to apply any of the rules preceding this one to any of the intermediate expansions.
\end{newer}

\item
Any form for which a \cd{defsetf}
or \cd{define-setf-method} declaration has been made.

\begin{newer}
X3J13 voted in March 1989 \issue{FUNCTION-NAME} to clarify that this
rule applies only when the function name in the form refers to a global function
definition and not to a locally defined function or macro.
\end{newer}

\end{itemize}

\begin{newer}
X3J13 voted in March 1989 \issue{FUNCTION-NAME} to add one more rule to
the preceding list, coming after all those listed above:
\begin{itemize}
\item  Any other list whose first element is a symbol (call it {\it f\/}).
     In this case, the call to \cd{setf} expands into a call to the function
     named by the
     list \cd{(setf~{\it f\/})} (see section~\ref{FUNCTION-NAME-SECTION}).
     The first argument is the new value and the
     remaining arguments are the values of the remaining elements of
     {\it place}.  This expansion occurs regardless of whether either {\it f\/} or
     \cd{(setf {\it f\/})} is defined as a function locally, globally, or not at
     all.  For example,
\begin{lisp}
(setf ({\it f\/} {\it arg1} {\it arg2} ...) {\it newvalue})
\end{lisp}
     expands into a form with the same effect and value as
\begin{lisp}
(let ((\#:temp1 {\it arg1})~~~~~;{\rm Force correct order of evaluation} \\*
~~~~~~(\#:temp2 {\it arg2}) \\*
~~~~~~... \\*
~~~~~~(\#:temp0 newvalue)) \\*
~~(funcall (function (setf {\it f\/})) \\*
~~~~~~~~~~~\#:temp0 \\*
~~~~~~~~~~~\#:temp1 \\*
~~~~~~~~~~~\#:temp2 ...))
\end{lisp}
By convention, any function named \cd{(setf {\it f\/})} should return its first
argument as its only value, in order to preserve the specification that
\cd{setf} returns its {\it newvalue}.
\end{itemize}
\end{newer}

\begin{new}
X3J13 voted in March 1989
\issue{SYMBOL-MACROLET-SEMANTICS} to add this case as well:
\begin{itemize}
\item A variable reference that refers to a symbol macro definition made by
\cd{symbol-\discretionary{}{}{}macrolet}, in which case \cd{setf} expands the reference and
then analyzes the resulting form.
\end{itemize}
\end{new}

\newpage%manual

\cd{setf} carefully arranges to preserve the usual left-to-right
order in which the various subforms are evaluated.
On the other hand,
the exact expansion for any particular form is not guaranteed and
may even be implementation-dependent; all that is guaranteed is that
the expansion of a \cd{setf} form will be an update form that works
for that particular implementation, and that the left-to-right evaluation
of subforms is preserved.

The ultimate result of evaluating a \cd{setf} form is the value
of {\it newvalue}.  Therefore \cd{(setf (car x) y)} does not expand
into precisely \cd{(rplaca x y)}, but into something more like
\begin{lisp}
(let ((G1 x) (G2 y)) (rplaca G1 G2) G2)
\end{lisp}
the precise expansion being implementation-dependent.

The user can define new \cd{setf} expansions by using \cd{defsetf}.

\begin{newer}
X3J13 voted in June 1989 \issue{SETF-MULTIPLE-STORE-VARIABLES}
to extend the specification of \cd{setf} to allow a {\it place}
whose \cd{setf} method has more than one store variable (see \cd{define-setf-method}).
In such a case as many values are accepted from the {\it newvalue} form
as there are store variables; extra values are ignored
and missing values default to \cd{nil},
as is usual in situations involving multiple values.

A proposal was submitted to X3J13 in September 1989
to add a \cd{setf} method for \cd{values} so that one could
in fact write, for example,
\begin{lisp}
(setf (values quotient remainder) \\
~~~~~~(truncate linewidth tabstop))
\end{lisp}
but unless this proposal is accepted users will have to
define a \cd{setf} method for \cd{values} themselves (not a difficult task).
\end{newer}
\end{defmac}

\begin{defmac}
psetf {place newvalue}*

\cd{psetf} is like \cd{setf} except that if more than one {\it place}-{\it newvalue}
pair is specified, then the assignments of new values to places are
done in parallel.  More precisely, all subforms that are to be evaluated
are evaluated from left to right; after all evaluations have been performed,
all of the assignments are performed in an unpredictable order.
(The unpredictability matters only if more than one {\it place} form
refers to the same place.)
\cd{psetf} always returns {\false}.

\begin{newer}
X3J13 voted in June 1989 \issue{SETF-MULTIPLE-STORE-VARIABLES}
to extend the specification of \cd{psetf} to allow a {\it place}
whose \cd{setf} method has more than one store variable (see \cd{define-setf-method}).
In such a case as many values are accepted from the {\it newvalue} form
as there are store variables; extra values are ignored
and missing values default to \cd{nil},
as is usual in situations involving multiple values.
\end{newer}
\end{defmac}

\begin{defmac}
shiftf {place}+ newvalue

Each {\it place} form may be any form acceptable
as a generalized variable to \cd{setf}.
In the form \cd{(shiftf {\it place1} {\it place2} ... {\it placen} {\it newvalue})},
the values in {\it place1} through {\it placen} are accessed and saved,
and {\it newvalue} is evaluated, for a total of ${\it n}+1$ values in all.
Values 2 through ${\it n}+1$ are then stored into {\it place1} through {\it placen},
and value 1 (the original value of {\it place1}) is returned.
It is as if all the places form a shift register; the {\it newvalue}
is shifted in from the right, all values shift over to the left one place,
and the value shifted out of {\it place1} is returned.  For example:
\begin{lisp}
(setq x (list 'a 'b 'c)) \EV\ (a b c) \\
 \\
(shiftf (cadr x) 'z) \EV\ b \\
~~~{\rm and now} x \EV\ (a z c) \\
 \\
(shiftf (cadr x) (cddr x) 'q) \EV\ z \\
~~~{\rm and now} x \EV\ (a (c) . q)
\end{lisp}
The effect of \cd{(shiftf {\it place1} {\it place2} ... {\it placen} {\it newvalue})}
is equivalent to
\begin{lisp}
(let (({\it var1} {\it place1}) \\
~~~~~~({\it var2} {\it place2}) \\
~~~~~~... \\
~~~~~~({\it varn} {\it placen})) \\
~~(setf {\it place1} {\it var2}) \\
~~(setf {\it place2} {\it var3}) \\
~~... \\
~~(setf {\it placen} {\it newvalue}) \\
~~{\it var1})
\end{lisp}
except that the latter would evaluate any subforms of each {\it place} twice,
whereas \cd{shiftf} takes care to evaluate them only once.
For example:
\begin{lisp}
(setq n 0) \\
(setq x '(a b c d)) \\
(shiftf (nth (setq n (+ n 1)) x) 'z) \EV\ b \\
~~~{\rm and now} x \EV\ (a z c d) \\[4pt]
{\it but} \\[4pt]
(setq n 0) \\
(setq x '(a b c d)) \\
(prog1 (nth (setq n (+ n 1)) x) \\*
~~~~~~~(setf (nth (setq n (+ n 1)) x) 'z)) \EV\ b \\
~~~{\rm and now} x \EV\ (a b z d)
\end{lisp}
Moreover, for certain {\it place} forms \cd{shiftf} may be
significantly more efficient than the \cd{prog1} version.

\begin{newer}
X3J13 voted in June 1989 \issue{SETF-MULTIPLE-STORE-VARIABLES}
to extend the specification of \cd{shiftf} to allow a {\it place}
whose \cd{setf} method has more than one store variable (see \cd{define-setf-method}).
In such a case as many values are accepted from the {\it newvalue} form
as there are store variables; extra values are ignored
and missing values default to \cd{nil},
as is usual in situations involving multiple values.
\end{newer}

\beforenoterule
\begin{rationale}
\cd{shiftf} and \cd{rotatef} have been included in Common Lisp
as generalizations of two-argument versions formerly called \cd{swapf}
and \cd{exchf}.  The two-argument versions have been found to be
very useful, but the names were easily confused.  The generalization
to many argument forms and the change of names were both inspired
by the work of Suzuki \cite{SUZUKI-POINTER-ROTATION},
which indicates that use of these primitives can make certain complex
pointer-manipulation programs clearer and easier to prove correct.
\end{rationale}
\afternoterule
\end{defmac}

\begin{defmac}
rotatef {place}*

Each {\it place} form may be any form acceptable
as a generalized variable to \cd{setf}.
In the form \cd{(rotatef {\it place1} {\it place2} ... {\it placen})},
the values in {\it place1} through {\it placen} are accessed and saved.
Values 2 through {\it n} and value 1 are then stored into {\it place1} through {\it placen}.
It is as if all the places form an end-around shift register
that is rotated one place to the left, with the value of {\it place1}
being shifted around the end to {\it placen}.
Note that \cd{(rotatef {\it place1} {\it place2})} exchanges the contents
of {\it place1} and {\it place2}.

The effect of \cd{(rotatef {\it place1} {\it place2} ... {\it placen})}
is roughly equivalent to
\begin{lisp}
(psetf {\it place1} {\it place2} \\
~~~~~~~{\it place2} {\it place3} \\
~~~~~~~... \\
~~~~~~~{\it placen} {\it place1})
\end{lisp}
except that the latter would evaluate any subforms of each {\it place} twice,
whereas \cd{rotatef} takes care to evaluate them only once.
Moreover, for certain {\it place} forms \cd{rotatef} may be
significantly more efficient.

\cd{rotatef} always returns {\false}.

\begin{newer}
X3J13 voted in June 1989 \issue{SETF-MULTIPLE-STORE-VARIABLES}
to extend the specification of \cd{rotatef} to allow a {\it place}
whose \cd{setf} method has more than one store variable (see \cd{define-setf-method}).
In such a case as many values are accepted from the {\it newvalue} form
as there are store variables; extra values are ignored
and missing values default to \cd{nil},
as is usual in situations involving multiple values.
\end{newer}
\end{defmac}

Other macros that manipulate generalized variables include
\cd{getf}, \cd{remf},
\cd{incf}, \cd{decf}, \cd{push}, \cd{pop},
\cd{assert}, \cd{ctypecase}, and \cd{ccase}.

Macros that manipulate generalized variables must guarantee the ``obvious''
semantics:  subforms of generalized-variable references are
evaluated exactly as many times as they appear in the source program, and
they are evaluated in exactly the same order as they appear in the source
program.

In generalized-variable references such as \cd{shiftf}, \cd{incf}, \cd{push},
and \cd{setf} of \cd{ldb}, the generalized variables are both read and
written in the same reference.   Preserving the source program order of
evaluation and the number of evaluations is particularly important.

As an example of these semantic rules, in the generalized-variable
reference \cd{(setf {\it reference} {\it value})} the {\it value} form
must be evaluated {\it after} all the subforms of the reference because
the {\it value} form appears to the right of them.

The expansion of these macros must consist of code that follows these
rules or has the same effect as such code.  This is accomplished by
introducing temporary variables bound to the subforms of the reference.
As an optimization in the implementation,
temporary variables may be eliminated whenever it
can be proved that removing them has no effect on the semantics of the program.
For example, a constant need never be saved in a temporary variable.
A variable, or for that matter any form that does not have side effects, need not be
saved in a temporary variable if it can be proved that its value will
not change within the scope of the generalized-variable reference.

Common Lisp provides built-in facilities to take care of
these semantic complications and optimizations.  Since the required
semantics can be guaranteed by these facilities, the user does not
have to worry about writing correct code for them, especially in
complex cases.  Even experts can become confused and make mistakes
while writing this sort of code.

\begin{newer}
X3J13 voted in March 1988 \issue{PUSH-EVALUATION-ORDER}
to clarify the preceding discussion about the order of evaluation of
subforms in calls to \cd{setf} and related macros.
The general intent is clear: evaluation
proceeds from left to right whenever possible. However, the left-to-right rule does not
remove the obligation on writers of macros and \cd{define-setf-method} to work
to ensure left-to-right order of evaluation.

Let it be emphasized that, in the following discussion,
a {\it form} is something whose syntactic use is such that it will
be evaluated.  A {\it subform} means a form that is nested inside another form,
not merely any Lisp object nested inside a form regardless of syntactic context. 

The evaluation ordering of subforms within a generalized variable
reference is determined by the order specified by the second value returned by
\cd{get-setf-method}.  For all predefined generalized variable references
(\cd{getf}, \cd{ldb}), this order of evaluation is exactly left-to-right.
When a generalized
variable reference is derived from a macro expansion, this rule is applied
{\it after} the macro is expanded to find the appropriate generalized variable
reference. 

This is intended to make it clear that if the user writes a \cd{defmacro} or
\cd{define-setf-method} macro that doesn't preserve left-to-right
evaluation order, the order specified in the
user's code holds.  For example, given
\begin{lisp}
(defmacro wrong-order (x y) {\Xbq}(getf ,y ,x))
\end{lisp}
then
\begin{lisp}
(push {\it value} (wrong-order {\it place1} {\it place2}))
\end{lisp}
will evaluate {\it place2} first and then {\it place1} because that is the order they
are evaluated in the macro expansion.
 
For the macros that manipulate generalized variables (\cd{push}, \cd{pushnew}, \cd{getf},
\cd{remf}, \cd{incf}, \cd{decf}, \cd{shiftf}, \cd{rotatef},
\cd{psetf}, \cd{setf}, \cd{pop}, and those defined with
\cd{define-modify-macro}) the subforms of the macro call are evaluated exactly once
in left-to-right order, with the subforms of the generalized variable
references evaluated in the order specified above.

Each of
\cd{push}, \cd{pushnew}, \cd{getf}, \cd{remf}, \cd{incf}, \cd{decf},
\cd{shiftf}, \cd{rotatef}, \cd{psetf}, and \cd{pop} evaluates
all subforms before modifying any of the generalized variable locations.  Moreover,
\cd{setf} itself,
in the case when a call on it has more than two arguments, performs its
operation on each pair in sequence.  That is, in
\begin{lisp}
(setf {\it place1} {\it value1} {\it place2} {\it value2} ...)
\end{lisp}
the subforms of {\it place1} and {\it value1} are evaluated, the
location specified by {\it place1} is modified to contain the value returned by
{\it value1}, and then the rest of the \cd{setf} form is processed in a like manner.

For the macros \cd{check-type}, \cd{ctypecase}, and \cd{ccase}, subforms of the
generalized variable reference are evaluated once per test of a generalized
variable, but they may be
evaluated again if the type check fails (in the case of \cd{check-type}) or if none of
the cases holds (in \cd{ctypecase} or \cd{ccase}).

For the macro \cd{assert}, the order of evaluation of the generalized variable
references is not specified.
\end{newer}

Another reason for building in these functions is that the
appropriate optimizations will differ from implementation to
implementation.  In some implementations most of the optimization is
performed by the compiler, while in others a simpler compiler is used and
most of the optimization is performed in the macros.  The cost of
binding a temporary variable relative to the cost of other Lisp
operations may differ greatly between one implementation
and another, and some implementations may find it
best never to remove temporary variables except in the simplest cases.

A good example of the issues involved can be seen in the following
generalized-variable reference:
\begin{lisp}
(incf (ldb byte-field variable))
\end{lisp}
This ought to expand into something like
\begin{lisp}
(setq variable \\
~~~~~~(dpb (1+ (ldb byte-field variable)) \\
~~~~~~~~~~~byte-field \\
~~~~~~~~~~~variable))
\end{lisp}
In this expansion example we have
ignored the further complexity of returning the correct
value, which is the incremented byte, not the new value of \cd{variable}.
Note that the variable \cd{byte-field} is evaluated twice, and the
variable \cd{variable} is referred to three times:
once as the location in which to store a value,
and twice during the computation of that value.

Now consider this expression:
\begin{lisp}
(incf (ldb (aref byte-fields (incf i)) \\
~~~~~~~~~~~(aref (determine-words-array) i)))
\end{lisp}
It ought to expand into something like this:
\begin{lisp}
(let ((temp1 (aref byte-fields (incf i))) \\
~~~~~~(temp2 (determine-words-array))) \\
~~(setf (aref temp2 i) \\
~~~~~~~~(dpb (1+ (ldb temp1 (aref temp2 i))) \\
~~~~~~~~~~~~~temp1 \\
~~~~~~~~~~~~~(aref temp2 i))))
\end{lisp}
Again we have ignored the complexity of returning the correct value.
What is important here is that the expressions \cd{(incf i)}
and \cd{(determine-words-array)}
must not be duplicated because each may have a side effect or
be affected by side effects.

\begin{newer}
X3J13 voted in January 1989 \issue{SETF-SUB-METHODS}
to specify more precisely the order of evaluation of subforms
when \cd{setf} is used with an access function that itself
takes a {\it place} as an argument, for example, \cd{ldb}, \cd{mask-field}, and
\cd{getf}.  (The vote also discussed the function \cd{char-bit},
but another vote \issue{CHARACTER-PROPOSAL} removed that function
from the language.)  The \cd{setf} methods for such accessors produce expansions
that effectively require explicit calls to \cd{get-setf-method}.

The code produced as the macro expansion of a \cd{setf} form that
itself admits a generalized variable as an argument must essentially
do the following major steps:
\begin{itemize}
\item It evaluates the value-producing subforms, in left-to-right order, and 
     binds the temporary variables to them; this is called {\it binding the temporaries}.

\item It reads the value from the generalized variable, using the supplied 
     accessing form, to get the old value;  this is called {\it doing the
     access}.  Note that this is done after all the evaluations of the 
     preceding step, including any side effects they may have.

\item It binds the store variable to a new value, and then installs this
     new value into the generalized variable using the supplied storing 
     form; this is called {\it doing the store}.
\end{itemize}
Doing the access for a generalized variable reference is not part of
the series of evaluations that must be done in left-to-right order. 

The place-specifier forms \cd{ldb}, \cd{mask-field}, and \cd{getf} admit (other)
{\it place} specifiers as arguments. During the \cd{setf} expansion of these forms, it 
is necessary to call \cd{get-setf-method} to determine how the inner, 
nested generalized variable must be treated.

    In a form such as
\begin{lisp}
(setf (ldb {\it byte-spec} {\it place-form}) {\it newvalue-form})
\end{lisp}
    the place referred to by the {\it place-form} must always be both accessed 
    and updated;  note that the update is to the generalized variable 
    specified by {\it place-form}, not to any object of type \cd{integer}.

    Thus this call to \cd{setf} should generate code to do the following:
\begin{itemize}
    \item Evaluate {\it byte-spec} and bind into a temporary
    \item Bind the temporaries for {\it place-form}
    \item Evaluate {\it newvalue-form} and bind into the store variable
    \item Do the access to {\it place-form}
    \item Do the store into {\it place-form} with the given bit-field of the
          accessed integer replaced with the value in the store variable
\end{itemize}
    If the evaluation of {\it newvalue-form} alters what is found in the 
    given {\it place}---such as setting a different bit-field of the
    integer---then the change of the bit-field denoted by
    {\it byte-spec} will be to that 
    altered integer, because the access step must be done after the {\it newvalue-form}
    evaluation.  Nevertheless, the 
    evaluations required for binding the temporaries are done before the
    evaluation of the {\it newvalue-form}, thereby preserving
    the required left-to-right evaluation order.

The treatment of \cd{mask-field} is similar to that of \cd{ldb}.

    In a form such as:
\begin{lisp}
(setf (getf {\it place-form} {\it ind-form}) {\it newvalue-form})
\end{lisp}
    the place referred to by the {\it place-form} must always be both accessed 
    and updated;  note that the update is to the generalized variable 
    specified by {\it place-form}, not necessarily to the particular list
    which is the property list in question.

    Thus this call to \cd{setf} should generate code to do the following:
\begin{itemize}
    \item Bind the temporaries for {\it place-form} 
    \item Evaluate {\it ind-form} and bind into a temporary
    \item Evaluate the {\it newvalue-form} and bind into the store variable
    \item Do the access to {\it place-form}
    \item Do the store into {\it place-form} with a possibly new property list
       obtained by combining the results of the evaluations and the access
\end{itemize}

    If the evaluation of {\it newvalue-form} alters what is found in the 
    given {\it place}---such as setting a different named property in the
    list---then the change of the property denoted by {\it ind-form} will be to that 
    altered list, because the access step is done after the {\it newvalue-form}
    evaluation.   Nevertheless, the 
    evaluations required for binding the temporaries are done before the
    evaluation of the {\it newvalue-form}, thereby preserving
    the required left-to-right evaluation order.

    Note that the phrase ``possibly new property list'' treats the 
    implementation of property lists as a ``black box''; it can mean that 
    the former property list is somehow destructively re-used, or it can 
    mean partial or full copying of it.  A side effect may or may not occur;
    therefore \cd{setf} must proceed as if the resultant property list
    were a different copy
    needing to be stored back into the generalized variable.
\end{newer}

The Common Lisp facilities provided to deal with these semantic issues include:
\begin{itemize}
\item
Built-in macros such as \cd{setf} and \cd{push} that follow the semantic rules.

\item
The \cd{define-modify-macro} macro, which allows new generalized-variable
manipulating macros (of a certain restricted kind) to be defined easily.
It takes care of the semantic rules automatically.

\item
The \cd{defsetf} macro, which allows new types of generalized-variable references
to be defined easily.  It takes care of the semantic rules automatically.

\item
The \cd{define-setf-method} macro and the \cd{get-setf-method} function, which
provide access to the internal mechanisms when it is necessary
to define a complicated new type of generalized-variable reference
or generalized-variable-manipulating macro.
\end{itemize}

\begin{newer}
Also important are the changes that allow lexical environments to be
used in appropriate ways in \cd{setf} methods.
\end{newer}

\begin{defmac}
define-modify-macro name lambda-list function [doc-string]

This macro defines a read-modify-write macro
named {\it name}.  An example of such a macro is \cd{incf}.  The first
subform of the macro will be a generalized-variable reference.
The {\it function} is literally the function to apply to the old contents of the
generalized-variable to get the new contents; it is not evaluated.
{\it lambda-list} describes
the remaining arguments for the {\it function}; these arguments come from
the remaining subforms of the macro after the generalized-variable reference.
{\it lambda-list} may contain \cd{\&optional} and \cd{\&rest} markers.
(The \cd{\&key} marker is not permitted here; \cd{\&rest} suffices for the purposes
of \cd{define-modify-macro}.)
{\it doc-string} is documentation for the macro {\it name} being defined.

The expansion of a \cd{define-modify-macro} is equivalent to the following, except
that it generates code that follows the semantic rules outlined above.
\begin{lisp}
(defmacro {\it name} ({\it reference} . {\it lambda-list}) \\
~~{\it doc-string} \\
~~{\Xbq}(setf ,{\it reference} \\
~~~~~~~~~({\it function} ,{\it reference} ,{\it arg1} ,{\it arg2} ...)))
\end{lisp}
where {\it arg1}, {\it arg2}, ..., are the parameters appearing in {\it lambda-list};
appropriate provision is made for a \cd{\&rest} parameter.

As an example, \cd{incf} could have been defined by:
\begin{lisp}
(define-modify-macro incf (\&optional (delta 1)) +)
\end{lisp}

An example of a possibly useful macro not predefined in Common Lisp is
\begin{lisp}
(define-modify-macro unionf (other-set \&rest keywords) union)
\end{lisp}

\begin{newer}
X3J13 voted in March 1988 \issue{GET-SETF-METHOD-ENVIRONMENT}
to specify that \cd{define-modify-macro} creates macros that
take \cd{\&environment} arguments and perform the
equivalent of correctly passing such lexical
environments to \cd{get-setf-method} in order to correctly maintain 
lexical references.
\end{newer}
\end{defmac}

\begin{defmac}
defsetf access-fn {update-fn [doc-string] |
                   lambda-list (store-variable)
                   <{declaration}* | doc-string> {\,form}*}

This defines how to \cd{setf} a generalized-variable reference
of the form \cd{({\it access-fn} ...)}.  The value of a generalized-variable
reference can always be obtained simply by evaluating it, so {\it access-fn}
should be the name of a function or a macro.

The user of \cd{defsetf} provides a description of how to store into the
generalized-variable reference and return the value that was stored (because
\cd{setf} is defined to return this value).  The implementation
of \cd{defsetf} takes care of
ensuring that subforms of the reference are evaluated exactly once and
in the proper left-to-right order.  In order to do this,
\cd{defsetf} requires that {\it access-fn} be a function or a macro
that evaluates its arguments, behaving like a function.
Furthermore, a \cd{setf} of a call on {\it access-fn} will also evaluate
all of {\it access-fn}'s arguments; it cannot treat any of them specially.
This means that \cd{defsetf} cannot be used to describe how to store into
a generalized variable that is a byte, such as \cd{(ldb field reference)}.
To handle situations that do not fit the restrictions imposed by \cd{defsetf},
use \cd{define-setf-method}, which gives the user additional control
at the cost of increased complexity.

A \cd{defsetf} declaration may take one of two forms.
The simple form is
\begin{lisp}
(defsetf {\it access-fn} {\it update-fn} \Mopt{{\it doc-string}})
\end{lisp}
The {\it update-fn} must name a function (or macro) that takes one more argument
than {\it access-fn} takes.  When \cd{setf} is given a {\it place}
that is a call on {\it access-fn}, it expands into
a call on {\it update-fn} that is given all the arguments to
{\it access-fn} and also, as its last argument, the new value
(which must be returned by {\it update-fn} as its value).
For example, the effect of
\begin{lisp}
(defsetf symbol-value set)
\end{lisp}
is built into the Common Lisp system.
This causes the expansion
\begin{lisp}
(setf (symbol-value foo) fu) \EX\ (set foo fu)
\end{lisp}
for example.  Note that
\begin{lisp}
(defsetf car rplaca)
\end{lisp}
would be incorrect because \cd{rplaca} does not return its last argument.

The complex form of \cd{defsetf} looks like
\begin{lisp}
(defsetf {\it access-fn} {\it lambda-list} ({\it store-variable}) . {\it body})
\end{lisp}
and resembles \cd{defmacro}.  The {\it body} must
compute the expansion of a \cd{setf} of a call on {\it access-fn}.

The {\it lambda-list} describes the arguments of {\it access-fn}.  \cd{\&optional},
\cd{\&rest}, and \cd{\&key} markers are permitted in {\it lambda-list}.
Optional arguments may
have defaults and ``supplied-p'' flags.  The {\it store-variable} describes the
value to be stored into the generalized-variable reference.

\beforenoterule
\begin{rationale}
The {\it store-variable} is enclosed
in parentheses to provide for an extension
to multiple store variables that would
receive multiple values from the second subform of \cd{setf}.
The rules given below for coding \cd{setf} methods discuss
the proper handling of multiple store variables to allow for
the possibility that this extension may be incorporated into Common Lisp
in the future.
\end{rationale}
\afternoterule

The {\it body} forms can be written as if the variables in the {\it lambda-list}
were bound to subforms of the call on {\it access-fn} and the
{\it store-variable} were bound to the second subform of \cd{setf}.
However, this is not actually the case.  During the evaluation of the
{\it body} forms, these variables are bound to names of temporary variables,
generated as if by \cd{gensym} or \cd{gentemp},
that will be bound by the
expansion of \cd{setf} to the values of those subforms.  This binding
permits the
{\it body} forms to be written without regard for order-of-evaluation
issues.  \cd{defsetf} arranges for the temporary variables to be
optimized out of the final result in cases where that is possible.  In
other words, an attempt is made by \cd{defsetf} to generate
the best code possible in a particular implementation.

Note that the code generated by the {\it body} forms must include provision
for returning the correct value (the value of {\it store-variable}).  This is
handled by the {\it body} forms rather than by \cd{defsetf} because
in many cases this value can be returned at no extra cost, by calling a
function that simultaneously stores into the generalized variable and
returns the correct value.

An example of the use of the complex form of \cd{defsetf}:
\begin{lisp}
(defsetf subseq (sequence start \&optional end) (new-sequence) \\
~~{\Xbq}(progn (replace ,sequence ,new-sequence \\
~~~~~~~~~~~~~~~~~~~:start1 ,start :end1 ,end) \\
~~~~~~~~~~,new-sequence))
\end{lisp}

\begin{newer}
X3J13 voted in March 1988 \issue{FLET-IMPLICIT-BLOCK}
to specify that the body of the expander function defined
by the complex form of \cd{defsetf} is implicitly enclosed in a \cd{block} construct
whose name is the same as the {\it name} of the {\it access-fn}.
Therefore \cd{return-from} may be used to exit from the function.
\end{newer}

\begin{newer}
X3J13 voted in March 1989 \issue{DEFINING-MACROS-NON-TOP-LEVEL}
to clarify that, while defining forms normally appear at top level,
it is meaningful to place them in non-top-level contexts; the complex form of
\cd{defsetf} must define the expander function
within the enclosing lexical environment, not within the global
environment.
\end{newer}
\end{defmac}

The underlying theory by which \cd{setf} and related macros arrange to
conform to the semantic rules given above is that from any
generalized-variable reference one may derive its ``\cd{setf} method,''
which describes how to store into that reference and which subforms of
it are evaluated.

\beforenoterule
\begin{incompatibility}
To avoid confusion,
it should be noted that the use of the word ``method'' here in connection
with \cd{setf} has nothing to do with its use in Lisp Machine Lisp in connection
with message-passing and the Lisp Machine Lisp ``flavor system.''
\begin{new}
And of course it also has nothing to do with the methods in
the Common Lisp Object System
\issue{CLOS}.
\end{new}
\end{incompatibility}
\afternoterule

Given knowledge of the subforms of the reference,
it is possible to avoid evaluating them multiple times or in the wrong
order.  A \cd{setf} method for a given access form can be expressed as
five values:
\begin{itemize}
\item
A list of {\it temporary variables}

\item
A list of {\it value forms} (subforms of the given form)
to whose values the temporary variables are to be bound

\item
A second list of temporary variables, called {\it store variables}

\item
A {\it storing form}

\item
An {\it accessing form}
\end{itemize}

The temporary variables will be bound to the values of
the value forms as if by \cd{let*}; that is, the
value forms will be evaluated in the order given
and may refer to the values of earlier value forms
by using the corresponding variables.

The store variables are to be bound to the values of the {\it newvalue} form,
that is, the values to be
stored into the generalized variable.  In almost all cases only a
single value is to be stored, and there is only one store variable.

The storing form and the accessing form may contain references to
the temporary variables (and also, in the case of the storing form,
to the store variables).  The accessing form returns the value of the
generalized variable.  The storing form modifies the value of the
generalized variable and guarantees to return the values of the
store variables as
its values; these are the correct values for \cd{setf} to
return.  (Again, in most cases there is a single store variable
and thus a single value to be returned.)
The value returned by the accessing form is, of course,
affected by execution of the storing form, but either of these
forms may be evaluated any number of times and therefore should be
free of side effects (other than the storing action of the storing form).

The temporary variables and the store variables are generated names,
as if by \cd{gensym} or \cd{gentemp},
so that there is never any problem of name clashes among them, or
between them and other variables in the program.  This is necessary to
make the special forms that do more than one \cd{setf} in parallel work
properly; these are \cd{psetf}, \cd{shiftf}, and \cd{rotatef}.  Computation
of the \cd{setf} method must always create new variable names; it may not return
the same ones every time.

Some examples of \cd{setf} methods for particular forms:
\begin{itemize}
\item
For a variable \cd{x}:
\begin{lisp}
() \\*
() \\*
(g0001) \\
(setq x g0001) \\*
x
\end{lisp}

\item
For \cd{(car {\it exp})}:
\begin{lisp}
(g0002) \\*
({\it exp}) \\*
(g0003)  \\
(progn (rplaca g0002 g0003) g0003) \\*
(car g0002)
\end{lisp}

\item
For \cd{(subseq {\it seq} {\it s} {\it e})}:
\begin{lisp}
(g0004 g0005 g0006) \\*
({\it seq} {\it s} {\it e}) \\*
(g0007) \\
(progn (replace g0004 g0007 :start1 g0005 :end1 g0006) \\*
~~~~~~~g0007) \\*
(subseq g0004 g0005 g0006)
\end{lisp}
\end{itemize}

\begin{defmac}
define-setf-method access-fn lambda-list
                   <{declaration}* | doc-string> {\,form}*

This defines how
to \cd{setf} a generalized-variable reference that is of the form
\cd{({\it access-fn}...)}.  The value of a generalized-variable reference can
always be obtained simply by evaluating it, so {\it access-fn} should be the
name of a function or a macro.

The {\it lambda-list} describes the subforms of the generalized-variable
reference, as with \cd{defmacro}.  The result of evaluating the
{\it forms} in the body must be five values representing
the \cd{setf} method, as described
above.  Note that \cd{define-setf-method} differs from the complex form of
\cd{defsetf} in that while the body is being executed the variables in
{\it lambda-list} are bound to parts of the generalized-variable reference,
not to temporary variables that will be bound to the values of such parts.
In addition, \cd{define-setf-method} does not have \cd{defsetf}'s
restriction that {\it access-fn} must be a function or a function-like
macro; an arbitrary \cd{defmacro} destructuring pattern is permitted in
{\it lambda-list}.

By definition there are no good small examples of \cd{define-setf-method}
because the easy cases can all be handled by \cd{defsetf}.
A typical use is to define the \cd{setf} method for \cd{ldb}:
\begin{obsolete}
\begin{lisp}
;;; SETF method for the form (LDB bytespec int). \\*
;;; Recall that the int form must itself be suitable for SETF. \\
(define-setf-method ldb (bytespec int) \\*
~~(multiple-value-bind (temps vals stores \\*
~~~~~~~~~~~~~~~~~~~~~~~~store-form access-form) \\*
~~~~~~(get-setf-method int)~~~~~~~~~;Get SETF method for int \\
~~~~(let ((btemp (gensym))~~~~~~~~~~;Temp var for byte specifier \\*
~~~~~~~~~~(store (gensym))~~~~~~~~~~;Temp var for byte to store \\*
~~~~~~~~~~(stemp (first stores)))~~~;Temp var for int to store \\
~~~~~~;; Return the SETF method for LDB as five values. \\*
~~~~~~(values (cons btemp temps)~~~~;Temporary variables \\*
~~~~~~~~~~~~~~(cons bytespec vals)~~;Value forms \\*
~~~~~~~~~~~~~~(list store)~~~~~~~~~~;Store variables \\
~~~~~~~~~~~~~~{\Xbq}(let ((,stemp (dpb ,store ,btemp ,access-form))) \\*
~~~~~~~~~~~~~~~~~,store-form \\*
~~~~~~~~~~~~~~~~~,store)~~~~~~~~~~~~~~~~~~~~~;Storing form \\*
~~~~~~~~~~~~~~{\Xbq}(ldb ,btemp ,access-form)~~~~~;Accessing form \\*
~~~~~~~~~~~~~~))))
\end{lisp}
\end{obsolete}

\begin{newer}
X3J13 voted in March 1988 \issue{GET-SETF-METHOD-ENVIRONMENT}
to specify that the \cd{\&environment} lambda-list keyword may appear in the
{\it lambda-list} in the same manner as for \cd{defmacro} in order
to obtain the lexical environment of the call to the \cd{setf} macro.
The preceding example should be modified to take advantage of
this new feature.  The \cd{setf} method must accept an \cd{\&environment}
parameter, which will receive the lexical environment of the call to \cd{setf};
this environment must then be given to \cd{get-setf-method} in order
that it may correctly use any locally bound \cd{setf} method that
might be applicable to the {\it place} form that appears as the second
argument to \cd{ldb} in the call to \cd{setf}.

\begin{lisp}
;;; SETF method for the form (LDB bytespec int). \\*
;;; Recall that the int form must itself be suitable for SETF. \\*
;;; Note the use of an \&environment parameter to receive the \\*
;;; lexical environment of the call for use with GET-SETF-METHOD. \\*
(define-setf-method ldb (bytespec int \&environment env) \\*
~~(multiple-value-bind (temps vals stores \\*
~~~~~~~~~~~~~~~~~~~~~~~~store-form access-form) \\*
~~~~~~(get-setf-method int env)~~~~~;Get SETF method for int \\
~~~~(let ((btemp (gensym))~~~~~~~~~~;Temp var for byte specifier \\*
~~~~~~~~~~(store (gensym))~~~~~~~~~~;Temp var for byte to store \\*
~~~~~~~~~~(stemp (first stores)))~~~;Temp var for int to store \\
~~~~~~;; Return the SETF method for LDB as five values. \\*
~~~~~~(values (cons btemp temps)~~~~;Temporary variables \\*
~~~~~~~~~~~~~~(cons bytespec vals)~~;Value forms \\*
~~~~~~~~~~~~~~(list store)~~~~~~~~~~;Store variables \\
~~~~~~~~~~~~~~{\Xbq}(let ((,stemp (dpb ,store ,btemp ,access-form))) \\*
~~~~~~~~~~~~~~~~~,store-form \\*
~~~~~~~~~~~~~~~~~,store)~~~~~~~~~~~~~~~~~~~~~;Storing form \\*
~~~~~~~~~~~~~~{\Xbq}(ldb ,btemp ,access-form)~~~~~;Accessing form \\*
~~~~~~~~~~~~~~))))
\end{lisp}
\end{newer}

\begin{newer}
X3J13 voted in March 1988 \issue{FLET-IMPLICIT-BLOCK}
to specify that the body of the expander function defined
by \cd{define-setf-method} is implicitly enclosed in a \cd{block} construct
whose name is the same as the {\it name} of the {\it access-fn}.
Therefore \cd{return-from} may be used to exit from the function.
\end{newer}

\begin{newer}
X3J13 voted in March 1989 \issue{DEFINING-MACROS-NON-TOP-LEVEL}
to clarify that, while defining forms normally appear at top level,
it is meaningful to place them in non-top-level contexts;
\cd{define-setf-method} must define the expander function
within the enclosing lexical environment, not within the global
environment.
\end{newer}
\end{defmac}

\begin{obsolete}
\begin{defun}[Function]
get-setf-method form

\cd{get-setf-method} returns
five values constituting the \cd{setf} method for {\it form}.
The {\it form} must be a
generalized-variable reference.  \cd{get-setf-method} takes care of
error-checking and macro expansion and guarantees to return exactly one
store variable.

As an example, an extremely simplified version of \cd{setf},
allowing no more and no fewer than two
subforms, containing no optimization to remove unnecessary variables, and
not allowing storing of multiple values, could be defined by:
\begin{lisp}
(defmacro setf (reference value) \\*
~~(multiple-value-bind (vars vals stores store-form access-form) \\*
~~~~~~(get-setf-method reference) \\
~~~~(declare (ignore access-form)) \\
~~~~{\Xbq}(let* ,(mapcar \#'list \\*
~~~~~~~~~~~~~~~~~~~~(append vars stores) \\*
~~~~~~~~~~~~~~~~~~~~(append vals (list value))) \\*
~~~~~~~,store-form)))
\end{lisp}
\end{defun}
\end{obsolete}

\begin{newer}
X3J13 voted in March 1988 \issue{GET-SETF-METHOD-ENVIRONMENT}
to add an optional environment argument to \cd{get-setf-method}.
The revised definition and example are as follows.

\begin{defun}[Function]
get-setf-method form &optional env

\cd{get-setf-method} returns
five values constituting the \cd{setf} method for {\it form}.
The {\it form} must be a
generalized-variable reference.
The {\it env} must be an environment of the sort obtained through
the \cd{\&environment} lambda-list keyword; if {\it env} is \cd{nil} or omitted,
the null lexical environment is assumed.
\cd{get-setf-method} takes care of
error checking and macro expansion and guarantees to return exactly one
store variable.

As an example, an extremely simplified version of \cd{setf},
allowing no more and no fewer than two
subforms, containing no optimization to remove unnecessary variables, and
not allowing storing of multiple values, could be defined by:
\begin{lisp}
(defmacro setf (reference value \&environment env) \\*
~~(multiple-value-bind (vars vals stores store-form access-form) \\*
~~~~~~(get-setf-method reference env)~~~~~;{\rm Note use of environment}\\
~~~~(declare (ignore access-form)) \\
~~~~{\Xbq}(let* ,(mapcar \#'list \\*
~~~~~~~~~~~~~~~~~~~~(append vars stores) \\*
~~~~~~~~~~~~~~~~~~~~(append vals (list value))) \\*
~~~~~~~,store-form)))
\end{lisp}
\end{defun}
\end{newer}

\begin{obsolete}
\begin{defun}[Function]
get-setf-method-multiple-value form

\cd{get-setf-method-multiple-value}
returns five values constituting the \cd{setf} method for {\it form}.
The {\it form} must be a
generalized-variable reference.  This is the same as \cd{get-setf-method}
except that it does not check the number of store variables; use this
in cases that allow storing multiple values into a generalized variable.
There are no such cases in standard Common Lisp, but this function is provided
to allow for possible extensions.
\end{defun}
\end{obsolete}

\begin{newer}
X3J13 voted in March 1988 \issue{GET-SETF-METHOD-ENVIRONMENT}
to add an optional environment argument to \cd{get-setf-method}.
The revised definition is as follows.

\begin{defun}[Function]
get-setf-method-multiple-value form &optional env

\cd{get-setf-method-multiple-value}
returns five values constituting the \cd{setf} method for {\it form}.
The {\it form} must be a
generalized-variable reference.
The {\it env} must be an environment of the sort obtained through
the \cd{\&environment} lambda-list keyword; if {\it env} is \cd{nil} or omitted,
the null lexical environment is assumed.

This is the same as \cd{get-setf-method}
except that it does not check the number of store variables; use this
in cases that allow storing multiple values into a generalized variable.
There are no such cases in standard Common Lisp, but this function is provided
to allow for possible extensions.
\end{defun}
\end{newer}

\begin{newer}
X3J13 voted in March 1988 \issue{GET-SETF-METHOD-ENVIRONMENT}
to clarify that a \cd{setf} method for a functional name is applicable
only when the global binding of that name is lexically visible.
If such a name has a local binding introduced by \cd{flet}, \cd{labels},
or \cd{macrolet}, then global definitions of \cd{setf} methods for
that name do not apply and are not visible.  All of the standard Common Lisp
macros that modify a \cd{setf} {\it place} (for example,
\cd{incf}, \cd{decf}, \cd{pop}, and \cd{rotatef}) obey this convention.
\end{newer}

\section{Function Invocation}

The most primitive form for function invocation in Lisp of course
has no name; any list that has no other interpretation
as a macro call or special form is taken to be a function call.
Other constructs are provided for less common but
nevertheless frequently useful situations.

\begin{defun}[Function]
apply function arg &rest more-args

This applies {\it function} to a list of arguments.
\begin{obsolete}
The {\it function} may be a
compiled-code object, or a lambda-expression, or a symbol; in the latter
case the global functional value of that symbol is used (but it is
illegal for the symbol to be the name of a macro or special form).
\end{obsolete}
\begin{newer}
X3J13 voted in June 1988 \issue{FUNCTION-TYPE} to allow the {\it function}
to be only of type \cd{symbol} or \cd{function}; a lambda-expression
is no longer acceptable as a functional argument.  One must use the
\cd{function} special form or the abbreviation \cd{\#'} before
a lambda-expression that appears as an  explicit argument form.
\end{newer}
The arguments for the {\it function} consist of the last argument
to \cd{apply} appended to the end of a list of all the other
arguments to \cd{apply} but the {\it function} itself;
it is as if all the arguments to \cd{apply} except the {\it function}
were given to \cd{list*} to create the argument list.
For example:
\begin{lisp}
(setq f '+) (apply f '(1 2)) \EV\ 3 \\
(setq f \#'-) (apply f '(1 2)) \EV\ -1 \\
(apply \#'max 3 5 '(2 7 3)) \EV\ 7 \\
(apply 'cons '((+ 2 3) 4)) {\EV} \\
~~~~~~~~((+ 2 3) . 4)	{\it not} (5 . 4) \\
(apply \#'+ '()) \EV\ 0
\end{lisp}
Note that if the function takes keyword arguments, the
keywords as well as the corresponding values must appear in the argument
list:
\begin{lisp}
(apply \#'(lambda (\cd{\&key} a b) (list a b)) '(:b 3)) \EV\ ({\nil} 3)
\end{lisp}
This can be very useful in conjunction with the \cd{\&allow-other-keys} feature:
\begin{lisp}
(defun foo (size \cd{\&rest} keys \cd{\&key} double \cd{\&allow-other-keys}) \\
~~(let ((v (apply \#'make-array size :allow-other-keys t keys))) \\
~~~~(if double (concatenate (type-of v) v v) v))) \\
 \\
(foo 4 :initial-contents '(a b c d) :double t) \\
~~~\EV\ \#(a b c d a b c d)
\end{lisp}
\end{defun}

\begin{defun}[Function]
funcall fn &rest arguments

\cd{(funcall {\it fn} {\it a1} {\it a2} ... {\it an})}
applies the function {\it fn} to the arguments
{\it a1}, {\it a2}, ..., {\it an}.
The {\it fn} may not
be a special form or a macro; this would not be meaningful.

\begin{newer}
X3J13 voted in June 1988 \issue{FUNCTION-TYPE} to allow the {\it fn}
to be only of type \cd{symbol} or \cd{function}; a lambda-expression
is no longer acceptable as a functional argument.  One must use the
\cd{function} special form or the abbreviation \cd{\#'} before
a lambda-expression that appears as an  explicit argument form.
\end{newer}

For example:
\begin{lisp}
(cons 1 2) \EV\ (1 . 2) \\
(setq cons (symbol-function '+)) \\
(funcall cons 1 2) \EV\ 3
\end{lisp}
The difference between \cd{funcall} and an ordinary function call is that
the function is obtained by ordinary Lisp evaluation rather than
by the special interpretation of the function position that normally
occurs.

\beforenoterule
\begin{incompatibility}
The Common Lisp function \cd{funcall} corresponds roughly to
the Interlisp primitive \cd{apply*}.
\end{incompatibility}
\afternoterule
\end{defun}


\begin{defun}[Constant]
call-arguments-limit

The value of \cd{call-arguments-limit} is a positive integer that is
the upper exclusive bound on the number of arguments that may
be passed to a function.  This bound depends on the implementation
but will not be smaller than 50.
(Implementors are encouraged to make this limit as large as practicable
without sacrificing performance.)
The value of \cd{call-arguments-limit} must be at
least as great as that of \cd{lambda-parameters-limit}.
See also \cd{multiple-values-limit}.
\end{defun}


\section{Simple Sequencing}

Each of the constructs in this section simply evaluates all the
argument forms in order.  They differ only in what results
are returned.

\begin{defspec}
progn {\,form}*

The \cd{progn} construct takes a number of forms and evaluates
them sequentially, in order, from left to right.  The values of all
the forms but the last are discarded; whatever the last form returns
is returned by the \cd{progn} form.
One says that all the forms but the last are evaluated for {\it effect},
because their execution is useful only for the side effects caused,
but the last form is executed for {\it value}.

\cd{progn} is the primitive control structure construct for ``compound
statements,'' such as {\bf begin}-{\bf end} blocks in
Algol-like languages.
Many Lisp constructs are ``implicit \cd{progn}'' forms:
as part of their syntax each allows many forms to be written
that are to be evaluated sequentially, discarding the results
of all forms but the last and returning the results of the last form.

If the last form of the \cd{progn} returns multiple values, then those
multiple values are returned by the \cd{progn} form.  If there are no forms
for the \cd{progn}, then the result is {\false}.  These rules generally hold for
implicit \cd{progn} forms as well.
\end{defspec}

\begin{defmac}
prog1 first {\,form}*

\cd{prog1} is similar to \cd{progn}, but it returns the value of
its {\it first} form.  All the argument forms are executed sequentially;
the value of the first form is saved while all the others are executed
and is then returned.

\cd{prog1} is most commonly used to evaluate an expression with side
effects and to return a value that must be computed {\it before} the side
effects happen.
For example:
\begin{lisp}
(prog1 (car x) (rplaca x 'foo))
\end{lisp}
alters the {\it car} of \cd{x} to be \cd{foo} and returns the old {\it car}
of \cd{x}.

\cd{prog1} always returns a single value, even if the first form
tries to return multiple values.
As a consequence,
\cd{(prog1 {\it x})} and \cd{(progn {\it x})} may behave differently
if {\it x} can produce multiple values.  See \cd{multiple-value-prog1}.
A point of style:
although \cd{prog1} can be used to force exactly a single value to
be returned, it is conventional to use the
function \cd{values} for this purpose.
\end{defmac}

\begin{defmac}
prog2 first second {\,form}*

\cd{prog2} is similar to \cd{prog1}, but it returns the value of
its {\it second} form.  All the argument forms are executed sequentially;
the value of the second form
is saved while all the other forms are executed and is then returned.
\cd{prog2} is provided mostly for historical compatibility.
\begin{lisp}
(prog2 {\it a} {\it b} {\it c} ... {\it z}) \EQ\ (progn {\it a} (prog1 {\it b} {\it c} ... {\it z}))
\end{lisp}
Occasionally it is desirable to perform one side effect, then a value-producing
operation, then another side effect.  In such a peculiar case, \cd{prog2}
is fairly perspicuous.
For example:
\begin{lisp}
(prog2 (open-a-file) (process-the-file) (close-the-file)) \\
\`;{\rm value is that of \cd{process-the-file}}
\end{lisp}

\cd{prog2}, like \cd{prog1},
always returns a single value, even if the second form
tries to return multiple values.  As a consequence of this,
\cd{(prog2 {\it x} {\it y})} and \cd{(progn {\it x} {\it y})} may behave differently
if {\it y} can produce multiple values.
\end{defmac}


\section{Establishing New Variable Bindings}
\label{VAR-BINDING-SECTION}

During the invocation of
a function represented by a lambda-expression (or a closure of
a lambda-expression, as produced by \cd{function}),
new bindings are established for the variables that are the
parameters of the lambda-expression.  These bindings initially
have values determined by the parameter-binding protocol discussed
in section~\ref{LAMBDA-EXPRESSIONS-SECTION}.

The following constructs may also be used to establish bindings of variables,
both ordinary and functional.

\begin{defspec}
let ({var | (var value)}*) {declaration}* {\,form}*

A \cd{let} form can be used to execute a series of forms
with specified variables bound to specified values.

More precisely, the form
\begin{lisp}
(let (({\it var1} {\it value1}) \\
~~~~~~({\it var2} {\it value2}) \\
~~~~~~... \\
~~~~~~({\it varm} {\it valuem})) \\
~~{\it declaration1} \\
~~{\it declaration2} \\
~~... \\
~~{\it declarationp} \\
~~{\it body1} \\
~~{\it body2} \\
~~... \\
~~{\it bodyn})
\end{lisp}
first evaluates the expressions {\it value1}, {\it value2}, and so on,
in that order, saving the resulting values.
Then all of the variables {\it varj} are bound to the corresponding
values in parallel; each binding will be a lexical binding unless
there is a \cd{special} declaration to the contrary.
The expressions {\it bodyk} are then evaluated
in order; the values of all but the last are discarded
(that is, the body of a \cd{let} form is an implicit \cd{progn}).
The \cd{let} form returns what evaluating {\it bodyn} produces (if the
body is empty, which is fairly useless, \cd{let} returns {\false} as its value).
The bindings of the variables have lexical scope and indefinite extent.

Instead of a list \cd{({\it varj} {\it valuej})}, one may write simply
{\it varj}.  In this case {\it varj} is initialized to {\false}.  As a matter
of style, it is recommended that {\it varj} be written only when that
variable will be stored into (such as by \cd{setq}) before its first
use.  If it is important that the initial value be {\false} rather than
some undefined value, then it is clearer to write out
\cd{({\it varj} {\false})} if the initial value is intended to mean ``false,'' or
\cd{({\it varj} '{\empty})} if the initial value is intended to be an empty
list.  Note that the code
\begin{lisp}
(let (x) \\
~~(declare (integer x)) \\
~~(setq x (gcd y z)) \\
~~...)
\end{lisp}
is incorrect; although \cd{x} is indeed set before it is used,
and is set to a value of the declared type \cd{integer}, nevertheless
\cd{x} momentarily takes on the value {\nil} in violation of the type
declaration.

Declarations may appear at the beginning of the body of a \cd{let}.
See \cd{declare}.

\begin{newer}
See also \cd{destructuring-bind}.
\end{newer}

\begin{new}
X3J13 voted in January 1989
\issue{VARIABLE-LIST-ASYMMETRY}
to regularize the binding formats for \cd{do}, \cd{do*}, \cd{let},
\cd{let*}, \cd{prog}, \cd{prog*}, and \cd{compiler-let}.
The new syntactic definition for \cd{let} makes the {\it value} optional:

\begin{defmac}
let ({var | (var [value])}*) {declaration}* {\,form}*

This changes \cd{let} to allow a list \cd{({\it var})} to appear,
meaning the same as simply {\it var}.
\end{defmac}
\end{new}
\end{defspec}

\begin{defspec}
let* ({var | (var value)}*) {declaration}* {\,form}*

\cd{let*} is similar to \cd{let}, but the bindings of variables
are performed sequentially rather than in parallel.  This allows
the expression for the value of a variable to refer to variables
previously bound in the \cd{let*} form.

More precisely, the form
\begin{lisp}
(let* (({\it var1} {\it value1}) \\
~~~~~~~({\it var2} {\it value2}) \\
~~~~~~~... \\
~~~~~~~({\it varm} {\it valuem})) \\
~~{\it declaration1} \\
~~{\it declaration2} \\
~~... \\
~~{\it declarationp} \\
~~{\it body1} \\
~~{\it body2} \\
~~... \\
~~{\it bodyn})
\end{lisp}
first evaluates the expression {\it value1}, then binds the variable
{\it var1} to that value; then it evaluates {\it value2} and binds {\it var2};
and so on.
The expressions {\it bodyj} are then evaluated
in order; the values of all but the last are discarded
(that is, the body of a \cd{let*} form is an implicit \cd{progn}).
The \cd{let*} form returns the results of evaluating {\it bodyn} (if the
body is empty, which is fairly useless, \cd{let*} returns {\false} as its value).
The bindings of the variables have lexical scope and indefinite extent.

Instead of a list \cd{({\it varj} {\it valuej})}, one may write simply {\it varj}.
In this case {\it varj} is initialized to {\false}.  As a matter of style,
it is recommended that {\it varj} be written only when that variable
will be stored into (such as by \cd{setq}) before its first use.
If it is important that the initial value be {\nil} rather than
some undefined value, then it is clearer to write out
\cd{({\it varj} {\false})} if the initial value is intended to mean ``false,'' or
\cd{({\it varj} '{\empty})} if the initial value is intended to be an empty
list.

Declarations may appear at the beginning of the body of a \cd{let*}.
See \cd{declare}.

\begin{new}
X3J13 voted in January 1989
\issue{VARIABLE-LIST-ASYMMETRY}
to regularize the binding formats for \cd{do}, \cd{do*}, \cd{let},
\cd{let*}, \cd{prog}, \cd{prog*}, and \cd{compiler-let}.
The new syntactic definition for \cd{let*} makes the {\it value} optional:

\begin{defmac}
let* ({var | (var [value])}*) {declaration}* {\,form}*

This changes \cd{let*} to allow a list \cd{({\it var})} to appear,
meaning the same as simply {\it var}.
\end{defmac}
\end{new}
\end{defspec}

\begin{obsolete}
\begin{defspec}*
compiler-let ({var | (var value)}*) {\,form}*

When executed by the Lisp interpreter, \cd{compiler-let} behaves
exactly like \cd{let} with all the variable bindings implicitly
declared \cd{special}.  When the compiler processes this form,
however, no code is compiled for the bindings;
instead, the processing of the body by the compiler
(including, in particular, the expansion of any macro calls
within the body) is done with
the special variables bound to the indicated values {\it in the
execution context of the compiler}.  This is primarily useful for
communication among complicated macros.

Declarations may {\it not} appear at the beginning of the body
of a \cd{compiler-let}.

\beforenoterule
\begin{rationale}
Because of the unorthodox
handling by \cd{compiler-let} of its variable bindings,
it would be complicated and confusing to permit declarations
that apparently referred to the variables bound by \cd{compiler-let}.
Disallowing declarations eliminates the problem.
\end{rationale}
\afternoterule

X3J13 voted in January 1989
\issue{VARIABLE-LIST-ASYMMETRY}
to regularize the binding formats for \cd{do}, \cd{do*}, \cd{let},
\cd{let*}, \cd{prog}, \cd{prog*}, and \cd{compiler-let}.
The new syntactic definition for \cd{compiler-let} makes the {\it value} optional:

\begin{defmac}
compiler-let ({var | (var [value])}*) {\,form}*

This changes \cd{compiler-let} to allow a list \cd{({\it var})} to appear,
meaning the same as simply {\it var}.
\end{defmac}
\end{defspec}
\end{obsolete}

\begin{newer}
X3J13 voted in June 1989 \issue{COMPILER-LET-CONFUSION} to remove
\cd{compiler-let} from the language.  Many uses of \cd{compiler-let}
can be replaced with more portable code that uses \cd{macrolet}
or \cd{symbol-macrolet}.
\end{newer}

\goodbreak

\begin{defspec}
progv symbols values {\,form}*

\cd{progv} is a special form that allows binding one or more dynamic
variables whose names may be determined at run time.  The sequence of
forms (an implicit \cd{progn})
is evaluated with the dynamic variables whose names are in the list
{\it symbols} bound to corresponding values from the list {\it values}.
(If too few values are supplied, the remaining symbols are bound and then
made to have no value; see \cd{makunbound}.  If too many values are
supplied, the excess values are ignored.)  The results of the \cd{progv}
form are those of the last
{\it form}.  The bindings of the dynamic variables are undone on
exit from the \cd{progv} form.  The lists of symbols and values are
computed quantities; this is what makes \cd{progv} different from, for
example, \cd{let}, where the variable names are stated explicitly in
the program text.

\cd{progv} is particularly useful for writing interpreters for languages
embedded in Lisp; it provides a handle on the mechanism for binding
dynamic variables.
\end{defspec}

\begin{defspec}
flet ({(name lambda-list
        <{declaration}* | doc-string> {\,form}*)}*)
     {\,form}* \\
labels ({(name lambda-list
          <{declaration}* | doc-string> {\,form}*)}*)
       {\,form}* \\
macrolet ({(name varlist
            <{declaration}* | doc-string> {\,form}*)}*)
         {\,form}*

\cd{flet} may be used to define locally named functions.  Within the
body of the \cd{flet} form, function names matching those defined
by the \cd{flet} refer to the locally defined functions rather than to
the global function definitions of the same name.

Any number of functions may be simultaneously defined.  Each definition
is similar in format to a \cd{defun} form: first a name,
then a parameter list (which may contain \cd{\&optional}, \cd{\&rest}, or \cd{\&key}
parameters), then optional declarations and documentation string,
and finally a body.
\begin{lisp}
(flet ((safesqrt (x) (sqrt (abs x)))) \\*
~~;; The safesqrt function is used in two places. \\*
~~(safesqrt (apply \#'+ (map 'list \#'safesqrt longlist))))
\end{lisp}

The \cd{labels} construct is identical in form to the \cd{flet} construct.
These constructs differ
in that the scope of the defined function names for \cd{flet}
encompasses only the body, whereas for \cd{labels} it encompasses the
function definitions themselves.  That is, \cd{labels} can be used to
define mutually recursive functions, but \cd{flet} cannot.  This
distinction is useful.  Using \cd{flet} one can locally redefine a global
function name, and the new definition can refer to the global definition;
the same construction using \cd{labels} would not have that effect.
\begin{lisp}
(defun integer-power (n k)~~~~~~~;A highly "bummed" integer \\*
~~(declare (integer n))~~~~~~~~~~; exponentiation routine \\*
~~(declare (type (integer 0 *) k)) \\
~~(labels ((expt0 (x k a) \\*
~~~~~~~~~~~~~(declare (integer x a) (type (integer 0 *) k)) \\*
~~~~~~~~~~~~~(cond ((zerop k) a) \\*
~~~~~~~~~~~~~~~~~~~((evenp k) (expt1 (* x x) (floor k 2) a)) \\*
~~~~~~~~~~~~~~~~~~~(t (expt0 (* x x) (floor k 2) (* x a))))) \\
~~~~~~~~~~~(expt1 (x k a) \\*
~~~~~~~~~~~~~(declare (integer x a) (type (integer 1 *) k)) \\*
~~~~~~~~~~~~~(cond ((evenp k) (expt1 (* x x) (floor k 2) a)) \\*
~~~~~~~~~~~~~~~~~~~(t (expt0 (* x x) (floor k 2) (* x a)))))) \\*
~~~~(expt0 n k 1)))
\end{lisp}

\cd{macrolet} is similar in form to \cd{flet} but defines local macros,
using the same format used by \cd{defmacro}.
The names established by \cd{macrolet} as names for macros are
lexically scoped.

\begin{new}
I have observed that, while most Common Lisp users pronounce \cd{macrolet}
to rhyme with ``silhouette,'' a small but vocal minority pronounce it
to rhyme with ``Chevrolet.''  A very few extremists furthermore
adjust their pronunciation
of \cd{flet} similarly: they say ``flay.''
Hey, hey!  {\it Tr\`es outr\'e.}
\end{new}

Macros often must be expanded at ``compile time'' (more generally,
at a time before the program itself is executed), and so
the run-time values of variables are not available to macros
defined by \cd{macrolet}.

\begin{obsolete}
The precise rule is that the macro-expansion
functions defined by \cd{macrolet} are defined in the {\it global} environment;
lexically scoped entities that would ordinarily be lexically apparent
are not visible within the expansion functions.
\end{obsolete}

\begin{newer}
X3J13 voted in March 1989 \issue{DEFINING-MACROS-NON-TOP-LEVEL}
to retract the previous sentence and specify that the macro-expansion
functions created by \cd{macrolet} are defined in the lexical environment in which
the \cd{macrolet} form appears, not in the null lexical environment.
Declarations, \cd{macrolet} definitions, and \cd{symbol-macrolet} definitions
affect code within the expansion functions in a \cd{macrolet}, but the
consequences are undefined if such code attempts to refer to
any local variable or function bindings that are visible in that
lexical environment.
\end{newer}

However,
lexically scoped entities {\it are} visible
within the body of the \cd{macrolet} form and {\it are} visible
to the code that is the expansion of a macro call.  The following example
should make this clear:
\begin{lisp}
;;; Example of scoping in macrolet. \\*
\\*
(defun foo (x flag) \\*
~~(macrolet ((fudge (z) \\*
~~~~~~~~~~~~~~~~;;{\rm The parameters \cd{x} and \cd{flag} are not accessible} \\*
~~~~~~~~~~~~~~~~;; {\rm at this point; a reference to \cd{flag} would be to} \\*
~~~~~~~~~~~~~~~~;; {\rm the global variable of that name.} \\*
~~~~~~~~~~~~~~~~{\Xbq}(if flag \\
~~~~~~~~~~~~~~~~~~~~~(* ,z ,z) \\
~~~~~~~~~~~~~~~~~~~~~,z))) \\
~~~~;;{\rm The parameters \cd{x} and \cd{flag} are accessible here.} \\*
~~~~(+ x \\*
~~~~~~~(fudge x) \\*
~~~~~~~(fudge (+ x 1)))))
\end{lisp}
The body of the \cd{macrolet} becomes
\begin{lisp}
(+ x \\*
~~~(if flag \\*
~~~~~~~(* x x) \\*
~~~~~~~x)) \\*
~~~(if flag \\*
~~~~~~~(* (+ x 1) (+ x 1)) \\*
~~~~~~~(+ x 1)))
\end{lisp}
after macro expansion.  The occurrences of \cd{x} and \cd{flag} legitimately
refer to the parameters of the function \cd{foo} because those parameters are
visible at the site of the macro call which produced the expansion.

\begin{newer}
X3J13 voted in March 1988 \issue{FLET-IMPLICIT-BLOCK}
to specify that the body of each function or expander function defined
by \cd{flet}, \cd{labels}, or \cd{macrolet}
is implicitly enclosed in a \cd{block} construct
whose name is the same as the {\it name} of the function.
Therefore \cd{return-from} may be used to exit from the function.
\end{newer}

\begin{newer}
X3J13 voted in March 1989 \issue{FUNCTION-NAME} to extend \cd{flet} and \cd{labels}
to accept any function-name (a symbol or a list
whose {\it car} is \cd{setf}---see section~\ref{FUNCTION-NAME-SECTION}) as a {\it name}
for a function to be locally defined.  In this way one can create local definitions
for \cd{setf} expansion functions.  (X3J13 explicitly declined to extend
\cd{macrolet} in the same manner.)
\end{newer}

\begin{new}
X3J13 voted in March 1988
\issue{FLET-DECLARATIONS}
to change \cd{flet}, \cd{labels}, and \cd{macrolet}
to allow declarations to appear before the body.
The new descriptions are therefore as follows:

\begin{defmac}
flet ({(name lambda-list
        <{declaration}* | doc-string> {\,form}*)}*)
     {declaration}* {\,form}* \\
labels ({(name lambda-list
          <{declaration}* | doc-string> {\,form}*)}*)
       {declaration}* {\,form}* \\
macrolet ({(name varlist
            <{declaration}* | doc-string> {\,form}*)}*)
         {declaration}* {\,form}*

These are now syntactically more similar to such
other binding forms as \cd{let}.

For \cd{flet} and \cd{labels}, the bodies of
the locally defined functions are part of
the scope of pervasive declarations appearing before the main body.
(This is consistent with the treatment of initialization forms in \cd{let}.)
For \cd{macrolet}, however, the bodies of
the locally defined macro expander functions are {\it not} included in
the scope of pervasive declarations appearing before the main body.
(This is consistent with the rule, stated below, that the bodies of
macro expander functions are in the global environment, not the local
lexical environment.)
Here is an example:
\begin{lisp}
(flet ((stretch (x) (* x *stretch-factor*)) \\*
~~~~~~~(chop (x) (- x *chop-margin*))) \\*
~~(declare (inline stretch chop))~~~;{\rm Illegal in original Common Lisp} \\
~~(if (> x *chop-margin*) (stretch (chop x)) (chop (stretch x))))
\end{lisp}
X3J13 voted to permit declarations of the sort noted above.
\end{defmac}
\end{new}
\end{defspec}


\begin{new}
\begin{defspec}
symbol-macrolet ({(var expansion)}*)
                {declaration}* {\,form}*

X3J13 voted in June 1988
\issue{CLOS}
to adopt the Common Lisp Object System.  Part of this proposal
is a general mechanism, \cd{symbol-macrolet},
for treating certain variable names as if they were
parameterless macro calls.  This facility may be useful independent of CLOS.
X3J13 voted in March 1989
\issue{SYMBOL-MACROLET-SEMANTICS}
to modify the definition of \cd{symbol-macrolet} substantially
and also voted
\issue{SYMBOL-MACROLET-DECLARE} to allow declarations before the body
of \cd{symbol-macrolet} but with peculiar treatment of \cd{special}
and type declarations.

The {\it forms} are executed as an implicit \cd{progn} in a lexical
environment that causes every reference to any defined {\it var}
to be replaced by the corresponding {\it expansion}.  It is as if
the reference to the {\it var} were a parameterless macro call;
the {\it expansion} is evaluated or otherwise processed
in place of the reference
\vadjust{\penalty-10000}%manual
(in particular, the expansion form is itself subject
to further expansion---this is one of the changes
\issue{SYMBOL-MACROLET-SEMANTICS}
from the
original definition in the CLOS proposal).  Note, however, that the names of
such symbol macros occupy the name space of variables, not the
name space of functions; just as one may have a function
(or macro, or special form) and a variable
with the same name without interference, so one may have an ordinary
macro (or function, or special form)
and a symbol macro with the same name.
The use of \cd{symbol-macrolet} can therefore be shadowed by \cd{let}
or other constructs that bind variables; \cd{symbol-macrolet} does
not substitute for all occurrences of a {\it var} as a variable
but only for those occurrences that would be construed as
references in the scope of a lexical binding of {\it var} as
a variable.  For example:
\begin{lisp}
(symbol-macrolet ((pollyanna 'goody)) \\*
~~(list pollyanna (let ((pollyanna 'two-shoes)) pollyanna))) \\*
~{\EV} (goody two-shoes){\rm, \it not} (goody goody)
\end{lisp}
% novel "Pollyanna" by Eleanor Porter, 1913
One might think that \cd{'goody} simply replaces all occurrences of
\cd{pollyanna}, and so the value of the \cd{let} would be
\cd{goody}; but this is not so.  A little reflection shows that under
this incorrect interpretation the body in expanded form would be
\begin{lisp}
(list 'goody (let (('goody 'two-shoes)) 'goody))
\end{lisp}
which is syntactically malformed.  The correct expanded form is
\begin{lisp}
(list 'goody (let ((pollyanna 'two-shoes)) pollyanna))
\end{lisp}
because the rebinding of \cd{pollyanna} by the \cd{let} form
shadows the symbol macro definition.

The {\it expansion} for each {\it var} is not evaluated at binding time
but only after it has replaced a reference to the {\it var}.
The \cd{setf} macro allows a symbol macro to be used as a {\it place},
in which case its expansion is used; moreover, \cd{setq} of a variable
that is really a symbol macro will be treated as if \cd{setf} had
been used.
The values of the last form are returned, or \cd{nil} if there is no value.

See \cd{macroexpand} and \cd{macroexpand-1}; they will expand symbol
macros as well as ordinary macros.

Certain {\it declarations} before the body are handled in a peculiar manner;
see section~\ref{DECLARE-SYNTAX-SECTION}.

%??? See the related CLOS features \cd{with-accessors} and \cd{with-slots}.
\end{defspec}
\end{new}

\section{Conditionals}

The traditional conditional construct in Lisp is \cd{cond}.
However, \cd{if} is much simpler and is directly comparable
to conditional constructs in other programming languages,
so it is considered to be primitive in Common Lisp and is described first.
Common Lisp also provides the dispatching constructs \cd{case} and \cd{typecase},
which are often more convenient than \cd{cond}.

\begin{defspec}
if test then [else]

The \cd{if} special form corresponds to the {\bf if}-{\bf then}-{\bf else} construct
found in most algebraic programming languages.
First the form {\it test} is evaluated.  If the result is not {\false},
then the form {\it then} is selected; otherwise the form {\it else} is selected.
Whichever form is selected is then evaluated, and \cd{if} returns
whatever is returned by evaluation of the selected form.
\begin{lisp}
(if {\it test} {\it then} {\it else}) \EQ\ (cond ({\it test} {\it then}) ({\true} {\it else}))
\end{lisp}
but \cd{if} is considered more readable in some situations.

The {\it else} form may be omitted, in which case if the value of {\it test}
is {\false} then nothing is done and the value of the \cd{if} form is {\false}.
If the value of
the \cd{if} form is important in this situation, then the \cd{and}
construct may be stylistically preferable,
depending on the context.
If the value is not important, but only the effect, then the \cd{when}
construct may be stylistically preferable.
\end{defspec}

\begin{defmac}
when test {\,form}*

\cd{(when {\it test} {\it form1} {\it form2} ... )}
first evaluates {\it test}.  If the result is {\false},
then no {\it form} is evaluated, and {\false} is returned.
Otherwise the {\it form}s constitute an implicit \cd{progn}
and are evaluated sequentially from left to right,
and the value of the last one is returned.
\begin{lisp}
(when {\it p} {\it a} {\it b} {\it c}) \EQ\ (and {\it p} (progn {\it a} {\it b} {\it c})) \\
(when {\it p} {\it a} {\it b} {\it c}) \EQ\ (cond ({\it p} {\it a} {\it b} {\it c})) \\
(when {\it p} {\it a} {\it b} {\it c}) \EQ\ (if {\it p} (progn {\it a} {\it b} {\it c}) {\false}) \\
(when {\it p} {\it a} {\it b} {\it c}) \EQ\ (unless (not {\it p}) {\it a} {\it b} {\it c})
\end{lisp}
As a matter of style,
\cd{when} is normally used to conditionally produce some side effects,
and the value of the \cd{when} form is normally not used.
If the value is relevant, then it may be
stylistically more appropriate to use \cd{and} or \cd{if}.
\end{defmac}

\begin{defmac}
unless test {\,form}*

\cd{(unless {\it test} {\it form1} {\it form2} ... )}
first evaluates {\it test}.  If the result is {\it not} {\false},
then the {\it form}s are not evaluated, and {\false} is returned.
Otherwise the {\it form}s constitute an implicit \cd{progn}
and are evaluated sequentially from left to right,
and the value of the last one is returned.
\begin{lisp}
(unless {\it p} {\it a} {\it b} {\it c}) \EQ\ (cond ((not {\it p}) {\it a} {\it b} {\it c})) \\
(unless {\it p} {\it a} {\it b} {\it c}) \EQ\ (if {\it p} {\false} (progn {\it a} {\it b} {\it c})) \\
(unless {\it p} {\it a} {\it b} {\it c}) \EQ\ (when (not {\it p}) {\it a} {\it b} {\it c})
\end{lisp}
As a matter of style,
\cd{unless} is normally used to conditionally produce some side effects,
and the value of the \cd{unless} form is normally not used.
If the value is relevant, then it may be
stylistically more appropriate to use \cd{if}.
\end{defmac}

\begin{defmac}
cond {(test {\,form}*)}*

A \cd{cond} form has a number (possibly zero) of
{\it clauses}, which are lists of forms.
Each clause consists of a {\it test} followed
by zero or more {\it consequents}.
For example:
\begin{lisp}
(cond ({\it test-1} {\it consequent-1-1} {\it consequent-1-2} ...) \\
~~~~~~({\it test-2}) \\
~~~~~~({\it test-3} {\it consequent-3-1} ...) \\
~~~~~~... )
\end{lisp}

The first clause whose {\it test} evaluates to non-{\false}
is selected; all other clauses are ignored, and the consequents
of the selected clause are evaluated in order (as an implicit \cd{progn}).

More specifically, \cd{cond} processes its clauses in order from left to
right.  For each clause, the {\it test} is evaluated.  If the result is
{\false}, \cd{cond} advances to the next clause.  Otherwise, the {\it cdr} of
the clause is treated as a list of forms, or consequents; these forms are
evaluated in order from left to right, as an implicit \cd{progn}.
After evaluating the consequents,
\cd{cond} returns without inspecting any remaining clauses.
The \cd{cond} special form returns the results
of evaluating the last of the selected consequents;
if there were no consequents in
the selected clause,
then the single (and necessarily non-null) value of the {\it test} is returned.
If \cd{cond} runs out of clauses (every test produced {\false},
and therefore no clause was selected), the value of the \cd{cond} form is
{\false}.

If it is desired to select the last clause unconditionally if all others
fail, the standard convention is to use {\true} for the {\it test}.
As a matter of style, it is desirable to write a last clause
\cd{({\true} {\false})} if the value of the \cd{cond} form is to be used
for something.  Similarly, it is in questionable
taste to let the last clause of
a \cd{cond} be a ``singleton clause''; an explicit {\true} should be provided.
(Note moreover that \cd{(cond ... ({\it x}))} may behave differently from
\cd{(cond ... ({\true} {\it x}))} if {\it x} might produce multiple values;
the former always returns a single value, whereas the latter returns whatever
values {\it x} returns.  However, as a matter of style it is preferable
to obtain this behavior by writing \cd{(cond ... (t (values {\it x})))},
using the \cd{values} function explicitly to indicate the discarding
of any excess values.)
For example:
\begin{lisp}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\=\kill
(setq z (cond (a 'foo) (b 'bar)))\>;{\rm Possibly confusing} \\*
(setq z (cond (a 'foo) (b 'bar) ({\true} {\false})))\>;{\rm Better} \\
(cond (a b) (c d) (e))\>;{\rm Possibly confusing} \\*
(cond (a b) (c d) ({\true} e))\>;{\rm Better} \\*
(cond (a b) (c d) ({\true} (values e)))\>;{\rm Better (if one value} \\*
                                       \>;~{\rm needed)} \\
(cond (a b) (c))\>;{\rm Possibly confusing} \\
(cond (a b) (t c))\>;{\rm Better} \\*
(if a b c)\>;{\rm Also better}
\end{lisp}
A Lisp \cd{cond} form may be compared to a continued {\bf if}-{\bf then}-{\bf else}
as found in many algebraic programming languages:
\begin{lisp}
~~~~~~~~~~~~~~~~~~~~\=~~~~~~~~~~~~~~~~~~~~~\=\kill
(cond ({\it p} ...)\>\>{\bf if} {\it p} {\bf then} ... \\
~~~~~~({\it q} ...)\>\hbox to 6pc{\hss\rm roughly\hss}\>{\bf else} {\bf if} {\it q} {\bf then} ... \\
~~~~~~({\it r} ...)\>\hbox to 6pc{\hss\rm corresponds\hss}\>{\bf else} {\bf if} {\it r} {\bf then} ... \\
~~~~~~...\>\hbox to 6pc{\hss\rm to\hss}\>... \\
~~~~~~({\true} ...))\>\>{\bf else} ...
\end{lisp}
\end{defmac}

\begin{defmac}
case keyform {({({key}*) | key} {\,form}*)}*

\cd{case} is a conditional that chooses one of its clauses to execute
by comparing a value to various constants, which are
typically keyword symbols, integers, or characters
(but may be any objects).  Its form is as follows:
\begin{lisp}
(case {\it keyform} \\
~~({\it keylist-1} {\it consequent-1-1} {\it consequent-1-2} ...) \\
~~({\it keylist-2} {\it consequent-2-1} ...) \\
~~({\it keylist-3} {\it consequent-3-1} ...) \\
~~...)
\end{lisp}
Structurally \cd{case} is much like \cd{cond},
and it behaves like \cd{cond}
in selecting one clause and then executing all consequents of that clause.
However, \cd{case} differs in the mechanism of clause selection.

The first thing \cd{case} does is to evaluate the form {\it keyform}
to produce an object called the {\it key object}.
Then \cd{case} considers
each of the clauses in turn.  If {\it key} is in the {\it keylist}
(that is, is \cd{eql} to any item in the {\it keylist}) of a clause,
the consequents of that
clause are evaluated as an implicit \cd{progn};
\cd{case} returns what was returned by the last
consequent (or {\false} if there are no consequents in that clause).
If no clause is satisfied, \cd{case} returns {\false}.

The keys in the keylists are {\it not} evaluated; literal key values
must appear in the keylists.
It is an error for the same key to appear in more than one clause;
a consequence is that the order of the clauses does not affect
the behavior of the \cd{case} construct.

Instead of a {\it keylist}, one may write one of the symbols
{\true} and \cd{otherwise}.  A clause with such a symbol
always succeeds and must be the last clause (this is an exception
to the order-independence of clauses).
See also \cd{ecase} and \cd{ccase}, each of which provides
an implicit \cd{otherwise} clause to signal an error if no clause
is satisfied.

If there is only one key for a clause, then that key may be written
in place of a list of that key, provided that no ambiguity results.
Such a ``singleton key'' may not be {\nil} (which is confusable
with {\empty}, a list of no keys), {\true}, \cd{otherwise}, or a cons.

\beforenoterule
\begin{incompatibility}
The Lisp Machine Lisp \cd{caseq} construct
uses \cd{eq} for the comparison.
In Lisp Machine Lisp \cd{caseq} therefore works for
fixnums but not bignums.
The MacLisp \cd{caseq} construct simply prohibits the use of bignums;
indeed, it permits only fixnums and symbols as clause keys.
In the interest of hiding the fixnum-bignum distinction,
and for general language consistency,
\cd{case} uses \cd{eql} in Common Lisp.

The Interlisp \cd{selectq} construct is similar to \cd{case}.
\end{incompatibility}
\afternoterule
\end{defmac}

\begin{defmac}
typecase keyform {(type {\,form}*)}*

\cd{typecase} is a conditional that chooses one of its clauses by
examining the type of an object.
Its form is as follows:
\begin{lisp}
(typecase {\it keyform} \\*
~~({\it type-1} {\it consequent-1-1} {\it consequent-1-2} ...) \\*
~~({\it type-2} {\it consequent-2-1} ...) \\*
~~({\it type-3} {\it consequent-3-1} ...) \\
~~...)
\end{lisp}
Structurally \cd{typecase} is much like \cd{cond} or \cd{case},
and it behaves like them
in selecting one clause and then executing all consequents of that clause.
It differs in the mechanism of clause selection.

The first thing \cd{typecase} does is to evaluate the form {\it keyform}
to produce an object called the key object.
Then \cd{typecase} considers
each of the clauses in turn.  The {\it type} that appears
in each clause is a type specifier; it is not evaluated
but is a literal type specifier.
The first clause for which the key
is of that clause's specified {\it type}
is selected, the consequents of this
clause are evaluated as an implicit \cd{progn},
and \cd{typecase} returns what was returned by the last
consequent (or {\false} if there are no consequents in that clause).
If no clause is satisfied, \cd{typecase} returns {\false}.

As for \cd{case}, the symbol {\true} or \cd{otherwise} may be written
for {\it type} to indicate that the clause should always be selected.
See also \cd{etypecase} and \cd{ctypecase}, each of which provides
an implicit \cd{otherwise} clause to signal an error if no clause
is satisfied.

It is permissible for more than one clause to specify a given type,
particularly if one is a subtype of another; the earliest applicable
clause is chosen.  Thus for \cd{typecase}, unlike \cd{case}, the order
of the clauses may affect the behavior of the construct.
For example:
\begin{lisp}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\=\kill
(typecase an-object \\
~~~(string ...)\>;{\rm This clause handles strings} \\
~~~((array t) ...)\>;{\rm This clause handles general arrays} \\
~~~((array bit) ...)\>;{\rm This clause handles bit arrays} \\
~~~(array ...)\>;{\rm This handles all other arrays} \\
~~~((or list number) ...)\>;{\rm This handles lists and numbers} \\
~~~(t ...))\>;{\rm This handles all other objects}
\end{lisp}
A Common Lisp compiler may choose to issue a warning if
a clause cannot be selected because it is completely shadowed by
earlier clauses.
\end{defmac}

\section{Blocks and Exits}
\label{BLOCK-RETURN-SECTION}

The \cd{block} and \cd{return-from} constructs provide a structured lexical
non-local exit facility.  At any point lexically within a \cd{block}
construct, a \cd{return-from} with the same name may be used to
perform an immediate transfer of control that
exits from the \cd{block}.  In the most common cases this mechanism is
more efficient than the dynamic non-local exit facility
provided by \cd{catch} and \cd{throw}, described in
section~\ref{CATCH-THROW-SECTION}.

\begin{defspec}
block name {\,form}*

The \cd{block} construct executes each {\it form} from left to right,
returning whatever is returned by the last {\it form}.
If, however, a \cd{return} or \cd{return-from} form that specifies the
same {\it name} is executed
during the execution of some {\it form}, then the results
specified by the \cd{return} or \cd{return-from} are immediately
returned as the value of the \cd{block} construct, and execution
proceeds as if the \cd{block} had terminated normally.
In this, \cd{block} differs from \cd{progn}; the \cd{progn} construct
has nothing to do with \cd{return}.

The {\it name} is not evaluated; it must be a symbol.
The scope of the {\it name} is lexical; only a \cd{return} or \cd{return-from}
textually contained in some {\it form} can exit from the block.
The extent of the name is dynamic.
Therefore it is only possible to exit from a given run-time incarnation of a
block once, either normally or by explicit return.

The \cd{defun} form implicitly puts a \cd{block} around the
body of the function defined; the \cd{block} has the same name as the function.
Therefore one may use \cd{return-from} to return
prematurely from a function defined by \cd{defun}.

The lexical scoping of the block name
is fully general and has consequences that may be surprising
to users and implementors of other Lisp systems.
For example, the \cd{return-from} in the following example actually does
work in Common Lisp as one might expect:
\begin{lisp}
(block loser \\
~~~(catch 'stuff \\
~~~~~~(mapcar \#'(lambda (x) (if (numberp x) \\
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(hairyfun x) \\
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(return-from loser {\nil}))) \\
~~~~~~~~~~~~~~items)))
\end{lisp}
Depending on the situation, a \cd{return} in Common Lisp
may not be simple.
A \cd{return} can break up catchers if necessary to get
to the block in question.
It is possible for a ``closure'' created by \cd{function} for
a lambda-expression to refer to a block name as long as the name
is lexically apparent.
\end{defspec}

\begin{defspec}
return-from name [result]

\cd{return-from}
is used to return from a \cd{block} or from such constructs
as \cd{do} and \cd{prog} that implicitly establish a \cd{block}.
The {\it name} is not evaluated and must be a symbol.
A \cd{block} construct with the same name must lexically
enclose the occurrence of \cd{return-from};
whatever the evaluation of {\it result} produces
is immediately returned from the block.
(If the {\it result} form is omitted, it defaults to {\nil}.
As a matter of style, this form ought to be used to indicate that
the particular value returned doesn't matter.)

The \cd{return-from} form itself never returns and cannot have a value;
it causes results to be returned from a \cd{block} construct.
If the evaluation of {\it result} produces multiple values,
those multiple values are returned by the construct exited.
\end{defspec}

\begin{defmac}
return [result]

\cd{(return {\it form})} is identical in meaning
to \cd{(return-from {\nil} {\it form})}; it returns from a block named {\nil}.
Blocks established implicitly by iteration constructs such
as \cd{do} are named {\nil}, so that \cd{return} will exit properly from
such a construct.
\end{defmac}

\section{Iteration}
\indexterm{iteration}

Common Lisp provides a number of iteration constructs.  The \cd{loop}
construct provides a trivial iteration facility; it is little more
than a \cd{progn} with a branch from the bottom back to the top.
The \cd{do}
and \cd{do*} constructs provide a general iteration facility
for controlling the variation of several variables on each cycle.
For specialized iterations
over the elements of a list or {\it n} consecutive integers, \cd{dolist} and
\cd{dotimes} are provided.  The \cd{tagbody} construct is the most
general, permitting arbitrary \cd{go} statements within it.  (The
traditional \cd{prog} construct is a synthesis of \cd{tagbody},
\cd{block}, and \cd{let}.)
Most of the iteration constructs permit statically defined non-local exits
(see \cd{return-from} and \cd{return}).

\subsection{Indefinite Iteration}

The \cd{loop} construct is the simplest iteration facility.
It controls no variables, and simply executes its body repeatedly.

\begin{defmac}
loop {\,form}*

Each {\it form} is evaluated in turn from left to right.
When the last {\it form} has been evaluated, then the first {\it form}
is evaluated again, and so on, in a never-ending cycle.
The \cd{loop} construct never returns a value.  Its execution must be terminated
explicitly, using \cd{return} or \cd{throw}, for example.

\cd{loop}, like most iteration constructs,
establishes an implicit block named {\nil}.
Thus \cd{return} may be used to exit from a \cd{loop} with specified results.

\begin{obsolete}
A \cd{loop} construct has this meaning only if every {\it form} is
non-atomic (a list).  The case where some {\it form} is
atomic is reserved for future extensions.

\beforenoterule
\begin{implementation}
There have been several proposals for a powerful iteration
mechanism to be called \cd{loop}.  One version is provided in Lisp Machine Lisp.
Implementors are encouraged to experiment with extensions to the \cd{loop}
syntax, but users should be advised that in all likelihood some specific
set of extensions to \cd{loop} will be adopted in a future revision of Common Lisp.
\end{implementation}
\afternoterule
\end{obsolete}

\begin{new}
X3J13 voted in January 1989
\issue{LOOP-FACILITY}
to include just such an extension of \cd{loop}.  See chapter~\ref{LOOP}.
\end{new}
\end{defmac}


\subsection{General Iteration}

In contrast to \cd{loop}, \cd{do} and \cd{do*} provide a powerful
and general mechanism for repetitively recalculating many variables.

\begin{defmac}
do ({(var [init [step]])}*)
   (end-test {result}*)
   {declaration}* {tag | statement}* \\
do* ({(var [init [step]])}*)
    (end-test {result}*)
    {declaration}* {tag | statement}*

The \cd{do} special form provides a generalized iteration facility,
with an arbitrary number of ``index variables.''
These variables are bound within the iteration and stepped in parallel
in specified ways.  They may be used both to generate successive
values of interest (such as successive integers) or to accumulate results.
When an end condition is met, the iteration terminates with a specified value.

In general, a \cd{do} loop looks like this:
\begin{lisp}
(do (({\it var1} {\it init1} {\it step1}) \\
~~~~~({\it var2} {\it init2} {\it step2}) \\
~~~~~... \\
~~~~~({\it varn} {\it initn} {\it stepn})) \\
~~~~({\it end-test} . {\it result}) \\
~~\Mstar{{\it declaration}} \\
~~. {\it tagbody})
\end{lisp}
A \cd{do*} loop looks exactly the same except that the name \cd{do} is
replaced by \cd{do*}.

The first item in the form is a list of zero or more index-variable
specifiers.  Each index-variable specifier is a list of the name of a
variable {\it var}, an initial value {\it init},
and a stepping form {\it step}.
If {\it init} is omitted, it defaults to {\false}.
If {\it step} is omitted, the {\it var} is not changed by the \cd{do} construct
between repetitions (though code within the \cd{do} is free to alter
the value of the variable by using \cd{setq}).

An index-variable specifier can also be just the name of a variable.
In this case, the variable has an initial value of {\false} and is
not changed between repetitions.
As a matter
of style, it is recommended that an unadorned variable name
be written only when that
variable will be stored into (such as by \cd{setq}) before its first
use.  If it is important that the initial value be {\false} rather than
some undefined value, then it is clearer to write out
\cd{({\it varj} {\false})} if the initial value is intended to mean ``false,'' or
\cd{({\it varj} '{\empty})} if the initial value is intended to be an empty
list.

\begin{new}
X3J13 voted in January 1989
\issue{VARIABLE-LIST-ASYMMETRY}
to regularize the binding formats for \cd{do}, \cd{do*}, \cd{let},
\cd{let*}, \cd{prog}, \cd{prog*}, and \cd{compiler-let}.
In the case of \cd{do} and \cd{do*} the first edition was inconsistent;
the formal syntax fails to reflect the fact that a simple variable
name may appear, as described in the preceding paragraph.  The
definitions should read

\begin{defmac}
do ({var | (var [init [step]])}*)
   (end-test {result}*)
   {declaration}* {tag | statement}* \\
do* ({var | (var [init [step]])}*)
    (end-test {result}*)
    {declaration}* {tag | statement}*

for consistency with the reading of the first edition and the X3J13 vote.
\end{defmac}
\end{new}

Before the first iteration, all the {\it init} forms are evaluated, and
each {\it var} is bound to the value of its respective {\it init}.
This is a binding, not an assignment; when the loop terminates,
the old values of those variables will be restored.
For \cd{do}, {\it all} of the {\it init} forms are evaluated {\it before} any {\it var}
is bound; hence all the
{\it init} forms may refer to the old bindings of all the variables
(that is, to the values visible before beginning execution of
the \cd{do} construct).
For \cd{do*}, the first {\it init} form is evaluated, then the first
{\it var} is bound to that value, then the second {\it init} form
is evaluated, then the second {\it var} is bound, and so on;
in general, the {\it initj} form can refer to the {\it new} binding {\it vark}
if ${\it k\/}<{\it j}$, and otherwise to the {\it old} binding of {\it vark}.

The second element of the loop is a list of an end-testing
predicate form {\it end-test} and zero or more {\it result} forms.
This resembles a \cd{cond} clause.
At the beginning of each iteration, after processing the variables,
the {\it end-test} is evaluated.  If the result is
{\false}, execution proceeds with the body of the \cd{do} (or \cd{do*}) form.
If the
result is not {\false}, the {\it result} forms are evaluated in order
as an implicit \cd{progn},
\indexterm{implicit \cd{progn}}
and then \cd{do} returns.  \cd{do} returns the results of evaluating
the last {\it result} form.
If there are no {\it result} forms, the value of \cd{do} is {\false}.
Note that this is not quite analogous to the treatment of
clauses in a \cd{cond} form, because a \cd{cond} clause
with no {\it result} forms returns the (non-{\nil}) result of the test.

At the beginning of each iteration other than the first, the
index variables are updated as follows.  All the {\it step} forms
are evaluated, from left to right, and the resulting values are
assigned to the respective index variables.
Any variable that has no associated {\it step} form is not assigned to.
For \cd{do}, all the {\it step} forms are evaluated before any variable
is updated; the assignment of values to variables is done in parallel,
as if by \cd{psetq}.
Because {\it all} of the {\it step} forms are evaluated before {\it any}
of the variables are altered, a {\it step} form when evaluated always has
access to the {\it old} values of {\it all} the index variables,
even if other {\it step} forms precede it.
For \cd{do*}, the first {\it step} form is evaluated, then the
value is assigned to the first {\it var}, then the second {\it step} form
is evaluated, then the value is assigned to the second {\it var}, and so on;
the assignment of values to variables is done sequentially,
as if by \cd{setq}.
For either \cd{do} or \cd{do*},
after the variables have been updated,
the {\it end-test} is evaluated as described above, and the iteration continues.

If the {\it end-test} of a \cd{do} form is \cd{{\false}},
the test will never succeed.
Therefore this provides an idiom for ``do forever'':
the {\it body} of the \cd{do} is executed repeatedly, stepping variables
as usual.  (The \cd{loop} construct performs
a ``do forever'' that steps no variables.)
The infinite loop can be terminated by the use of \cd{return},
\cd{return-from}, \cd{go} to an outer level, or \cd{throw}.
For example:
\begin{lisp}
(do ((j 0 (+ j 1))) \\
~~~~({\false})~~~~~~~~~~~~~~~~~~~~~~~~;{\rm Do forever} \\
~~(format t "{\Xtilde}\%Input {\Xtilde}D:" j) \\
~~(let ((item (read))) \\
~~~~(if (null item) (return)~~~~~;{\rm Process items until {\false} seen} \\
~~~~~~~~(format t "{\Xtilde}\&Output {\Xtilde}D: {\Xtilde}S" j (process item)))))
\end{lisp}

The remainder of the \cd{do} form constitutes an implicit \cd{tagbody}.
Tags may appear within the body of a \cd{do} loop
for use by \cd{go} statements appearing in the body (but such \cd{go}
statements may not appear in the variable specifiers, the {\it end-test},
or the {\it result} forms).
When the end of a \cd{do} body is reached, the next iteration cycle
(beginning with the evaluation of {\it step} forms) occurs.

An implicit \cd{block} named {\nil} surrounds the entire \cd{do} form.
A \cd{return} statement may be used at any point to exit the loop
immediately.

\cd{declare} forms may appear at the beginning of a \cd{do} body.
They apply to code in the \cd{do} body, to the bindings of the \cd{do}
variables, to the {\it init} forms, to the {\it step} forms,
to the {\it end-test}, and to the {\it result} forms.

\beforenoterule
\begin{incompatibility}
``Old-style'' MacLisp \cd{do} loops, that is, those
of the form \cd{(do {\it var} {\it init} {\it step} {\it end-test} . {\it body})},
are not supported in Common Lisp.
Such old-style loops are considered obsolete
and in any case are easily converted to a new-style
\cd{do} with the insertion of three pairs of parentheses.
In practice the compiler can catch nearly all instances of old-style
\cd{do} loops because they will not have a legal format anyway.
\end{incompatibility}
\afternoterule

Here are some examples of the use of \cd{do}:
\begin{lisp}
(do ((i 0 (+ i 1))~~~~~;{\rm Sets every null element of \cd{a-vector} to zero} \\*
~~~~~(n (length a-vector))) \\*
~~~~((= i n)) \\
~~(when (null (aref a-vector i)) \\*
~~~~(setf (aref a-vector i) 0)))
\end{lisp}
The construction
\begin{lisp}
(do ((x e (cdr x)) \\*
~~~~~(oldx x x)) \\*
~~~~((null x)) \\*
~~{\it body})
\end{lisp}
exploits parallel assignment to index variables.  On the first
iteration, the value of \cd{oldx} is whatever value \cd{x} had before
the \cd{do} was entered.  On succeeding iterations, \cd{oldx} contains
the value that \cd{x} had on the previous iteration. 

Very often an iterative algorithm can be most clearly expressed entirely
in the {\it step} forms of a \cd{do}, and the {\it body} is empty.
For example,
\begin{lisp}
(do ((x foo (cdr x)) \\*
~~~~~(y bar (cdr y)) \\*
~~~~~(z '{\empty} (cons (f (car x) (car y)) z))) \\
~~~~((or (null x) (null y)) \\*
~~~~~(nreverse z)))
\end{lisp}
does the same thing as \cd{(mapcar \#'f foo bar)}.  Note that the {\it step}
computation for \cd{z} exploits the fact that variables are stepped in parallel.
Also, the body of the loop is empty.  Finally, the use of \cd{nreverse}
to put an accumulated \cd{do} loop result into the correct order
is a standard idiom.  Another example:
\begin{lisp}
(defun list-reverse (list) \\*
~~~~~~~(do ((x list (cdr x)) \\*
~~~~~~~~~~~~(y '{\empty} (cons (car x) y))) \\*
~~~~~~~~~~~((endp x) y)))
\end{lisp}
Note the use of \cd{endp} rather than \cd{null} or \cd{atom}
to test for the end of a list; this may result in more robust code.

As an example of nested loops, suppose that \cd{env} holds a list
of conses.  The {\it car} of each cons is a list of symbols,
and the {\it cdr} of each cons is a list of equal length containing
corresponding values.  Such a data structure is similar to an association
list
but is divided into ``frames''; the overall structure resembles a rib cage.
A lookup function on such a data structure might be
\begin{lisp}
(defun ribcage-lookup (sym ribcage) \\*
~~~~~~~(do ((r ribcage (cdr r))) \\*
~~~~~~~~~~~((null r) {\false}) \\
~~~~~~~~~(do ((s (caar r) (cdr s)) \\*
~~~~~~~~~~~~~~(v (cdar r) (cdr v))) \\*
~~~~~~~~~~~~~((null s)) \\
~~~~~~~~~~~(when (eq (car s) sym) \\*
~~~~~~~~~~~~~(return-from ribcage-lookup (car v))))))
\end{lisp}
(Notice the use of indentation in the above example
to set off the bodies of the \cd{do} loops.)

A \cd{do} loop may be explained in terms of the more primitive constructs
\cd{block}, \cd{return}, \cd{let}, \cd{loop}, \cd{tagbody},
and \cd{psetq} as follows:
\begin{lisp}
(block nil \\*
~~(let (({\it var1} {\it init1}) \\*
~~~~~~~~({\it var2} {\it init2}) \\
~~~~~~~~... \\*
~~~~~~~~({\it varn} {\it initn})) \\*
~~~~\Mstar{{\it declaration}} \\
~~~~(loop (when {\it end-test} (return (progn . {\it result}))) \\*
~~~~~~~~~~(tagbody . {\it tagbody}) \\*
~~~~~~~~~~(psetq {\it var1} {\it step1} \\*
~~~~~~~~~~~~~~~~~{\it var2} {\it step2} \\*
~~~~~~~~~~~~~~~~~... \\*
~~~~~~~~~~~~~~~~~{\it varn} {\it stepn}))))
\end{lisp}
\cd{do*} is exactly like \cd{do} except that the bindings and steppings
of the variables are performed sequentially rather than in parallel.
It is as if, in the above explanation,
\cd{let} were replaced by \cd{let*} and \cd{psetq} were replaced
by \cd{setq}.
\end{defmac}

\subsection{Simple Iteration Constructs}

The constructs \cd{dolist} and \cd{dotimes} execute a body of code
once for each value taken by a single variable.  They are expressible
in terms of \cd{do}, but capture very common patterns of use.

Both \cd{dolist} and \cd{dotimes} perform
a body of statements repeatedly.  On each iteration a specified
variable is bound to an element of interest that the body may
examine.  \cd{dolist} examines successive elements of a list,
and \cd{dotimes} examines integers from 0 to ${\it n}-1$
for some specified positive integer {\it n}.

The value of any of these constructs may be specified by an optional result
form, which if omitted defaults to the value {\false}.

The \cd{return} statement may be used to return
immediately from a \cd{dolist} or \cd{dotimes} form,
discarding any following iterations
that might have been performed; in effect, a \cd{block} named {\nil}
surrounds the construct.
The body of the loop is implicitly a \cd{tagbody} construct;
it may contain tags to serve as the targets of \cd{go} statements.
Declarations may appear before the body of the loop.

\begin{defmac}
dolist (var listform [resultform])
       {declaration}* {tag | statement}*

\cd{dolist} provides straightforward iteration over the elements of a list.
First \cd{dolist}
evaluates the form {\it listform},
which should produce a list.  It then executes the body
once for each element in the list, in order, with
the variable {\it var} bound to the element.
Then {\it resultform} (a single form, {\it not} an implicit \cd{progn})
is evaluated, and the result is the value of the \cd{dolist}
form.  (When the {\it resultform} is evaluated, the control variable {\it var}
is still bound and has the value {\nil}.)
If {\it resultform} is omitted, the result is {\false}.

\begin{lisp}
(dolist (x '(a b c d)) (prin1 x) (princ " ")) \EV\ {\false} \\
~~~{\rm after printing ``\cd{a b c d }'' (note the trailing space)}
\end{lisp}

An explicit \cd{return} statement may be used to terminate the loop
and return a specified value.

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}
\end{defmac}

\begin{defmac}
dotimes (var countform [resultform])
        {declaration}* {tag | statement}*

\cd{dotimes} provides straightforward iteration over a sequence of integers.
The expression
\cd{(dotimes ({\it var} {\it countform} {\it resultform}) . {\it progbody})}
evaluates the form {\it countform}, which should produce an integer.  It then
performs {\it progbody} once for each integer from zero (inclusive) to
{\it count} (exclusive), in order, with the variable {\it var} bound to the
integer; if the value of {\it countform} is zero or negative,
then the {\it progbody} is
performed zero times.  Finally, {\it resultform} (a single form, {\it not} an
implicit \cd{progn}) is evaluated, and the result is the value of the
\cd{dotimes} form.  (When the {\it resultform} is evaluated, the control
variable {\it var} is still bound and has as its value the number of times
the body was executed.)
If {\it resultform} is omitted, the result is {\false}.

An explicit \cd{return} statement may be used to terminate the loop
and return a specified value.

Here is an example of the use of \cd{dotimes} in processing strings:
\begin{lisp}
;;; True if the specified subsequence of the string is a \\*
;;; palindrome (reads the same forwards and backwards). \\*
\\*
(defun palindromep (string \cd{\&optional} \\*
~~~~~~~~~~~~~~~~~~~~~~~~~~~(start 0) \\*
~~~~~~~~~~~~~~~~~~~~~~~~~~~(end (length string))) \\
~~(dotimes (k (floor (- end start) 2) {\true}) \\*
~~~~(unless (char-equal (char string (+ start k)) \\*
~~~~~~~~~~~~~~~~~~~~~~~~(char string (- end k 1))) \\*
~~~~~~(return {\false})))) \\
\\
(palindromep "Able was I ere I saw Elba") \EV\ {\true} \\
 \\
(palindromep "A man, a plan, a canal--Panama!") \EV\ {\false} \\
 \\
(remove-if-not \#'alpha-char-p~~~~~;{\rm Remove punctuation} \\*
~~~~~~~~~~~~~~~"A man, a plan, a canal--Panama!") \\*
~~~\EV\ "AmanaplanacanalPanama" \\
 \\
(palindromep \\*
~(remove-if-not \#'alpha-char-p \\*
~~~~~~~~~~~~~~~~"A man, a plan, a canal--Panama!")) \EV\ {\true} \\
 \\
(palindromep \\*
~(remove-if-not \\*
~~~\#'alpha-char-p \\*
~~~"Unremarkable was I ere I saw Elba Kramer, nu?")) \EV\ {\true} \\
 \\
(palindromep \\*
~(remove-if-not \\*
~~~\#'alpha-char-p \\*
~~~"A man, a plan, a cat, a ham, a yak, \\*
~~~~~~~~~~~~~~~~~~~a yam, a hat, a canal--Panama!")) \EV\ {\true}
\\
(palindromep \\*
~(remove-if-not \\*
~~~\#'alpha-char-p \\*
~~~"Ja-da, ja-da, ja-da ja-da jing jing jing")) \EV\ {\false}
\end{lisp}

Altering the value of {\it var} in the body of the loop (by using \cd{setq},
for example) will have unpredictable, possibly implementation-dependent
results.  A Common Lisp compiler may choose to issue a warning if such a variable
appears in a \cd{setq}.

\beforenoterule
\begin{incompatibility}
The \cd{dotimes} construct is the closest thing
in Common Lisp to the Interlisp \cd{rptq} construct.
\end{incompatibility}
\afternoterule
\end{defmac}

See also \cd{do-symbols}, \cd{do-external-symbols},
and \cd{do-all-symbols}.

\subsection{Mapping}
\indexterm{mapping}

Mapping is a type of iteration in which a function is 
successively applied to pieces of one or more sequences.
The result of the iteration is a sequence containing the respective
results of the function applications.
There are several options for the way in which the pieces of the list are
chosen and for what is done with the results returned by the applications of
the function.

The function \cd{map} may be used to map over any kind of sequence.
The following functions operate only on lists.

\begin{defun}[Function]
mapcar function list &rest more-lists \\
maplist function list &rest more-lists \\
mapc function list &rest more-lists \\
mapl function list &rest more-lists \\
mapcan function list &rest more-lists \\
mapcon function list &rest more-lists

For each of these mapping functions,
the first argument is a function and the rest must be lists.
The function must take as many arguments as there are lists.

\cd{mapcar} operates on successive elements of the lists.
First the function is applied to the {\it car} of each list,
then to the {\it cadr} of each list, and so on.
(Ideally all the lists are the same length; if not,
the iteration terminates when the shortest list runs out,
and excess elements in other lists are ignored.)
The value returned by \cd{mapcar} is a list of the
results of the successive calls to the function.
For example:
\begin{lisp}
(mapcar \#'abs '(3 -4 2 -5 -6)) \EV\ (3 4 2 5 6) \\
(mapcar \#'cons '(a b c) '(1 2 3)) \EV\ ((a . 1) (b . 2) (c . 3))
\end{lisp}

\cd{maplist} is like \cd{mapcar} except that the function is applied to
the lists and successive {\it cdr}'s of those lists rather than to successive
elements of the lists.
For example:
\begin{lisp}
(maplist \#'(lambda (x) (cons 'foo x)) \\*
~~~~~~~~~'(a b c d)) \\*
~~~\EV\ ((foo a b c d) (foo b c d) (foo c d) (foo d))
\end{lisp}

\begin{lisp}
(maplist \#'(lambda (x) (if (member (car x) (cdr x)) 0 1))) \\*
~~~~~~~~~'(a b a c d b c)) \\*
~~~\EV\ (0 0 1 0 1 1 1) \\*
~~~;{\rm An entry is \cd{1} if the corresponding element of the input} \\*
~~~;~{\rm list was the last instance of that element in the input list.}
\end{lisp}

\cd{mapl} and \cd{mapc} are like \cd{maplist} and \cd{mapcar},
respectively, except that they do not accumulate the results
of calling the function.

\beforenoterule
\begin{incompatibility}
In all Lisp systems since Lisp 1.5,
\cd{mapl} has been called \cd{map}.  In the chapter on sequences
it is explained why this was a bad choice.  Here the name \cd{map}
is used for the far more useful generic sequence mapper,
in closer accordance with the computer science literature,
especially the growing body of papers on functional programming.
\begin{new}
Note that this remark, predating the design of the Common Lisp Object System,
uses the term ``generic'' in a generic sense and not necessarily
in the technical sense used by CLOS
(see chapter~\ref{DTYPES}).
\end{new}
\end{incompatibility}
\afternoterule

These functions are used when the function is being called merely for its
side effects rather than for its returned values.
The value returned by \cd{mapl} or \cd{mapc} is the second argument,
that is, the first sequence argument.

\cd{mapcan} and \cd{mapcon} are like \cd{mapcar} and \cd{maplist}, respectively,
except that they combine the results of
the function using \cd{nconc} instead of \cd{list}.  That is,
\begin{lisp}
(mapcon {\it f} {\it x1} ... {\it xn}) \\
~~~\EQ\ (apply \#'nconc (maplist {\it f} {\it x1} ... {\it xn}))
\end{lisp}
and similarly for the relationship between \cd{mapcan} and \cd{mapcar}.
Conceptually, these functions allow the mapped function to return
a variable number of items to be put into the output list.
This is particularly useful for effectively returning zero or one item:
\begin{lisp}
(mapcan \#'(lambda (x) (and (numberp x) (list x))) \\
~~~~~~~~'(a 1 b c 3 4 d 5)) \\
~~~\EV\ (1 3 4 5)
\end{lisp}
In this case the function serves as a filter; this is a standard Lisp
idiom using \cd{mapcan}.
(The function \cd{remove-if-not} might have been useful in this
particular context, however.)
Remember that \cd{nconc} is a destructive operation, and therefore
so are \cd{mapcan} and \cd{mapcon}; the lists returned by the {\it function}
are altered in order to concatenate them.

Sometimes a \cd{do} or a straightforward recursion is preferable to a
mapping operation;  however, the mapping functions should be used wherever they
naturally apply because this increases the clarity of the code. 

The functional argument to a mapping function must be acceptable
to \cd{apply}; it cannot be a macro or the name of a special form.
Of course, there is nothing wrong with using a function that has \cd{\&optional}
and \cd{\&rest} parameters as the functional argument.

\begin{newer}
X3J13 voted in June 1988 \issue{FUNCTION-TYPE} to allow the {\it function}
to be only of type \cd{symbol} or \cd{function}; a lambda-expression
is no longer acceptable as a functional argument.  One must use the
\cd{function} special form or the abbreviation \cd{\#'} before
a lambda-expression that appears as an  explicit argument form.
\end{newer}

\begin{new}
X3J13 voted in January 1989
\issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict user side effects; see section~\ref{STRUCTURE-TRAVERSAL-SECTION}.
\end{new}
\end{defun}

\subsection{The ``Program Feature''}

Lisp implementations since Lisp 1.5 have had what was originally
called ``the program feature,'' as if it were impossible to write
programs without it!  The \cd{prog} construct allows one to
write in an Algol-like or Fortran-like statement-oriented
style, using \cd{go} statements that can refer to tags in the
body of the \cd{prog}.  Modern Lisp programming style tends to use
\cd{prog} rather infrequently.  The various iteration constructs,
such as \cd{do}, have bodies with the characteristics of a \cd{prog}.
(However, the ability to use \cd{go} statements within iteration
constructs is very seldom called upon in practice.)

Three distinct operations are performed by \cd{prog}: it binds local variables,
it permits use of the \cd{return} statement, and it permits use of the \cd{go}
statement.
In Common Lisp, these three operations have been separated into three
distinct constructs: \cd{let}, \cd{block}, and \cd{tagbody}.
These three constructs may be used independently as building blocks
for other types of constructs.

\begin{defspec}
tagbody {tag | statement}*

The part of a \cd{tagbody} after the variable list is called the {\it body}.
An item in the body may be a symbol or an integer, in which case it is called a
{\it tag}, or an item in the body may be a list, in which case it is called a 
{\it statement}.

Each element of the body is processed from left to right.
A {\it tag} is ignored; a {\it statement}
is evaluated, and its results are discarded.  If the end of the body
is reached, the \cd{tagbody} returns {\false}.

If \cd{(go {\it tag})} is evaluated, control jumps to the part of the body
labelled with the {\it tag}.

\beforenoterule
\begin{incompatibility}
The ``computed \cd{go}'' feature of MacLisp is not
supported.  The syntax of a computed \cd{go} is idiosyncratic,
and the feature is not supported by Lisp Machine Lisp, NIL (New Implementation of Lisp), or Interlisp.
The computed \cd{go} has been infrequently used in MacLisp anyway
and is easily simulated with no loss of
efficiency by using a \cd{case} statement each of whose
clauses performs a (non-computed) \cd{go}.
\end{incompatibility}
\afternoterule

The scope of the tags established by a \cd{tagbody} is lexical,
and the extent is dynamic.  Once a \cd{tagbody} construct has
been exited, it is no longer legal to \cd{go} to a {\it tag} in its body.
It is permissible for a \cd{go} to jump to a \cd{tagbody} that is not
the innermost \cd{tagbody} construct containing that \cd{go};
the tags established by a \cd{tagbody} will only shadow other tags
of like name.

The lexical scoping of the \cd{go} targets named by tags is
fully general and has consequences that may be surprising
to users and implementors of other Lisp systems.
For example, the \cd{go} in the following example actually does
work in Common Lisp as one might expect:
\begin{lisp}
(tagbody \\*
~~~(catch 'stuff \\*
~~~~~~(mapcar \#'(lambda (x) (if (numberp x) \\*
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(hairyfun x) \\*
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(go lose))) \\*
~~~~~~~~~~~~~~items)) \\
~~~(return) \\*
~lose \\*
~~~(error "I lost big!"))
\end{lisp}
Depending on the situation, a \cd{go} in Common Lisp does not necessarily
correspond to a simple machine ``jump'' instruction.
A \cd{go} can break up catchers if necessary to get
to the target.  It is possible for a ``closure'' created by \cd{function} for
a lambda-expression to refer to a \cd{go} target as long as the tag
is lexically apparent.  See chapter~\ref{SCOPE} for an elaborate
example of this.

\begin{new}
There are some holes in this specification (and that of \cd{go}) that
leave some room for interpretation.  For example, there is no explicit
prohibition against the same tag appearing more than once in the same
\cd{tagbody} body.  Every implementation I know of will complain
in the compiler, if not in the interpreter, if there is a \cd{go} to
such a duplicated tag; but some implementors take the position
that duplicate tags are permitted provided there is no \cd{go} to
such a tag.  (``If a tree falls in the forest, and there is no one
there to hear it, then no one needs to yell `Timber!'\thinspace'')
Also, some implementations allow objects other than symbols, integers,
and lists in the body and typically ignore them.
Consequently,
some programmers use redundant tags such as \cd{---} for formatting purposes,
and strings as comments:
\begin{lisp}
(defun dining-philosopher (j) \\*
~~(tagbody --- \\*
~~~think~~~(unless (hungry) (go think)) \\*
~~~~~~~~~~~--- \\
~~~~~~~~~~~"Can't eat without chopsticks." \\*
~~~~~~~~~~~(snatch (chopstick j)) \\*
~~~~~~~~~~~(snatch (chopstick (mod (+ j 1) 5))) \\*
~~~~~~~~~~~--- \\
~~~eat~~~~~(when (hungry) \\*
~~~~~~~~~~~~~(mapc \#'gobble-down \\*
~~~~~~~~~~~~~~~~~~~'(twice-cooked-pork kung-pao-chi-ding \\*
~~~~~~~~~~~~~~~~~~~~~wu-dip-har orange-flavor-beef \\*
~~~~~~~~~~~~~~~~~~~~~two-side-yellow-noodles twinkies)) \\*
~~~~~~~~~~~~~(go eat)) \\*
~~~~~~~~~~~--- \\
~~~~~~~~~~~"Can't think with my neighbors' stomachs rumbling." \\*
~~~~~~~~~~~(relinquish (chopstick j)) \\*
~~~~~~~~~~~(relinquish (chopstick (mod (+ j 1) 5))) \\*
~~~~~~~~~~~--- \\*
~~~~~~~~~~~(if (happy) (go think) \\*
~~~~~~~~~~~~~~~(become insurance-salesman))))
\end{lisp}
In certain implementations of Common Lisp they get away with it.
Others abhor what they view as an abuse of unintended ambiguity
in the language specification.  For maximum portability, I advise
users to steer clear of these issues.  Similarly, it is best
to avoid using \cd{nil} as a tag, even though it is a symbol, because
a few implementations treat \cd{nil} as a list to be executed.
To be extra careful, avoid calling from within a \cd{tagbody}
a macro whose expansion might not be a non-\cd{nil} list; wrap such a 
call in \cd{(progn~...)}, or rewrite the macro to return \cd{(progn~...)}
if possible.
\end{new}
\end{defspec}

\begin{defmac}
prog ({var | (var [init])}*) {declaration}* {tag | statement}* \\
prog* ({var | (var [init])}*) {declaration}* {tag | statement}*

The \cd{prog} construct is a synthesis of \cd{let}, \cd{block},
and \cd{tagbody}, allowing bound variables and the use of \cd{return} and \cd{go}
within a single construct.  A typical \cd{prog} construct looks like this:
\begin{lisp}
(prog ({\it var1} {\it var2} ({\it var3} {\it init3}) {\it var4} ({\it var5} {\it init5})) \\*
~~~~~~\Mstar{{\it declaration}} \\*
~~~~~~{\it statement1} \\
~{\it tag1} \\*
~~~~~~{\it statement2} \\*
~~~~~~{\it statement3} \\*
~~~~~~{\it statement4} \\
~{\it tag2} \\*
~~~~~~{\it statement5} \\*
~~~~~~... \\*
~~~~~~)
\end{lisp}
The list after the keyword \cd{prog} is a set of specifications for binding
{\it var1}, {\it var2}, etc.,
which are temporary variables bound locally to the \cd{prog}.
This list is processed exactly as the list in a \cd{let} statement:
first all the {\it init} forms are evaluated from left to right
(where {\false} is used for
any omitted {\it init} form), and then the variables are all bound in
parallel to the respective results.
Any {\it declaration} appearing in the \cd{prog} is used as if appearing
at the top of the \cd{let} body.

The body of the \cd{prog} is executed as if it were a \cd{tagbody}
construct; the \cd{go} statement may be used to transfer control
to a {\it tag}.

A \cd{prog} implicitly establishes a \cd{block} named {\nil} around
the entire \cd{prog} construct, so that \cd{return} may be used
at any time to exit from the \cd{prog} construct.

Here is a fine example of what can be done with \cd{prog}:
\begin{lisp}
(defun king-of-confusion (w) \\
~~"Take a cons of two lists and make a list of conses. \\
~~~Think of this function as being like a zipper." \\
~~(prog (x y z)~~~~~;{\rm Initialize \cd{x}, \cd{y}, \cd{z} to {\false}} \\
~~~~~~~~(setq y (car w) z (cdr w)) \\
~~~loop \\
~~~~~~~~(cond ((null y) (return x)) \\
~~~~~~~~~~~~~~((null z) (go err))) \\
~~~rejoin \\
~~~~~~~~(setq x (cons (cons (car y) (car z)) x)) \\
~~~~~~~~(setq y (cdr y) z (cdr z)) \\
~~~~~~~~(go loop) \\
~~~err \\
~~~~~~~~(cerror "Will self-pair extraneous items" \\
~~~~~~~~~~~~~~~~"Mismatch - gleep!  ~S" y) \\
~~~~~~~~(setq z y) \\
~~~~~~~~(go rejoin)))
\end{lisp}
which is accomplished somewhat more perspicuously by
\begin{lisp}
(defun prince-of-clarity (w) \\
~~"Take a cons of two lists and make a list of conses. \\
~~~Think of this function as being like a zipper." \\
~~(do ((y (car w) (cdr y)) \\
~~~~~~~(z (cdr w) (cdr z)) \\
~~~~~~~(x '{\empty} (cons (cons (car y) (car z)) x))) \\
~~~~~~((null y) x) \\
~~~~(when (null z) \\
~~~~~~(cerror "Will self-pair extraneous items" \\
~~~~~~~~~~~~~~"Mismatch - gleep!  ~S" y) \\
~~~~~~(setq z y))))
\end{lisp}

The \cd{prog} construct may be explained in terms of the simpler
constructs \cd{block}, \cd{let}, and \cd{tagbody} as
follows:
\begin{lisp}
(prog {\it variable-list} \Mstar{{\it declaration}} . {\it body}) \\
~~~\EQ\ (block nil (let {\it variable-list} \Mstar{{\it declaration}} (tagbody . {\it body})))
\end{lisp}

The \cd{prog*} special form is almost the same as \cd{prog}.  The only
difference is that the binding and initialization of the temporary
variables is done {\it sequentially}, so that the {\it init} form for each
one can use the values of previous ones.
Therefore \cd{prog*} is to \cd{prog} as \cd{let*} is to \cd{let}.
For example,
\begin{lisp}
(prog* ((y z) (x (car y))) \\
~~~~~~~(return x))
\end{lisp}
returns the {\it car} of the value of \cd{z}.

\begin{new}
I haven't seen \cd{prog} used very much in the last several years.
Apparently splitting it into functional constituents
(\cd{let}, \cd{block}, \cd{tagbody}) has been a success.  Common Lisp
programmers now tend to use whichever specific construct is appropriate.
\end{new}
\end{defmac}

\begin{defspec}
go tag

The \cd{(go {\it tag})} special form is used to do a ``go to'' within
a \cd{tagbody} construct.  The {\it tag} must be a symbol or an integer;
the {\it tag} is not evaluated.
\cd{go} transfers control to the point in the body labelled by a
tag \cd{eql} to the one given.  If there is no such tag in the body, the
bodies of lexically containing \cd{tagbody} constructs
(if any) are examined as well.
It is an error if there is no matching tag lexically visible
to the point of the \cd{go}.

The \cd{go} form does not ever return a value.

As a matter of style, it is recommended that the user think twice before
using a \cd{go}.  Most purposes of \cd{go} can be accomplished with one of
the iteration primitives, nested conditional forms, or
\cd{return-from}.  If the use of \cd{go} seems to be unavoidable,
perhaps the control structure implemented by \cd{go} should be packaged
as a macro definition.
\end{defspec}


\begin{new}
\section{Structure Traversal and Side Effects}
\label{STRUCTURE-TRAVERSAL-SECTION}

X3J13 voted in January 1989 \issue{MAPPING-DESTRUCTIVE-INTERACTION}
to restrict side effects during the course
of a built-in operation that can execute user-supplied code while
traversing a data structure.

Consider the following example:
\begin{lisp}
(let ((x '(apples peaches pumpkin pie))) \\*
~~(dolist (z x) \\*
~~~~(when (eq z 'peaches) \\*
~~~~~~(setf (cddr x) '(mango kumquat))) \\*
~~~~(format t "~S " (car z))))
\end{lisp}
Depending on the details of the implementation of \cd{dolist},
this bit of code could easily print
\begin{lisp}
apples peaches mango kumquat
\end{lisp}
(which is perhaps what was intended), but it might as easily print
\begin{lisp}
apples peaches pumpkin pie
\end{lisp}
Here is a plausible implementation of \cd{dolist} that
produces the first result:
\begin{lisp}
(defmacro dolist ((var listform \&optional (resultform ''nil)) \\*
~~~~~~~~~~~~~~~~~~\&body body) \\*
~~(let ((tailvar (gensym "DOLIST"))) \\*
~~~~{\Xbq}(do ((,tailvar ,listform (cdr ,tailvar))) \\*
~~~~~~~~~((null ,tailvar) ,resultform) \\*
~~~~~~~(let ((,var (car ,tailvar))) ,@body))
\end{lisp}
But here is a plausible implementation of \cd{dolist} that
produces the second result:
\begin{lisp}
(defmacro dolist ((var listform \&optional (resultform ''nil)) \\*
~~~~~~~~~~~~~~~~~~\&body body) \\*
~~(let ((tailvar (gensym "DOLIST"))) \\*
~~~~{\Xbq}(do ((,tailvar ,listform)) \\*
~~~~~~~~~((null ,tailvar) ,resultform) \\*
~~~~~~~(let ((,var (pop ,tailvar))) ,@body))
\end{lisp}

The X3J13 recognizes and legitimizes varying implementation practices:
in general it is an error for code executed during a ``structure-traversing''
operation to destructively modify the structure in a way that might
affect the ongoing traversal operation.  The committee identified in particular
the following special cases.

For list traversal operations, the {\it cdr} chain
may not be destructively modified.

For array traversal operations, the array may not be adjusted
(see \cd{adjust-array}) and its fill pointer, if any, may not be modified.

For hash table operations (such as \cd{with-hash-table-iterator}
and \cd{maphash}), new entries may not be added or deleted,
{\it except} that the very entry being processed by user code
may be changed or deleted.

For package symbol operations (for example, \cd{with-package-iterator}
and \cd{do-symbols}), new symbols may not be interned in,
nor symbols uninterned from, the packages being traversed or
any packages they use, {\it except} that the very symbol
being processed by user code may be uninterned.

X3J13 noted that this vote is intended to clarify restrictions
on the use of structure traversal operations that are not themselves
inherently destructive; for example, it applies to \cd{map} and \cd{dolist}.
Destructive operators such as \cd{delete} require even more complicated
restrictions and are addressed by a separate proposal.

The X3J13 vote did not specify a complete list of the operations to which these
restrictions apply.  Table~\ref{TRAVERSAL-OPERATIONS-TABLE}
shows what I believe to be a complete list of operations
that traverse structures and take user code as a body (in the case of
macros) or as a functional argument (in the case of functions).

In addition, note that user code should not modify list
structure that might be undergoing interpretation by the evaluator,
whether explicitly invoked via \cd{eval} or implicitly invoked,
for example as in the case of a hook function (a \cd{defstruct}
print function, the value of \cd{*evalhook*} or \cd{*applyhook*}, etc.)
that happens to be a closure of interpreted code.  Similarly, \cd{defstruct}
print functions and other hooks should not perform side effects
on data structures being printed or being processed by \cd{format}, or on a
string given to \cd{make-string-input-stream}.  You get the idea;
be sensible.

Note that an operation such as \cd{mapcar} or \cd{dolist} traverses
not only {\it cdr} pointers (in order to chase down the list)
but also {\it car} pointers (in order to obtain the elements themselves).
The restriction against modification appears to apply to all these pointers.
\end{new}

\begin{table}[t]
\begin{new}
\leavevmode
\vtop{
\caption{Structure Traversal Operations Subject to Side Effect Restrictions}
\label{TRAVERSAL-OPERATIONS-TABLE}
}

\begingroup\cf \tabcolsep0pt\relax
\begin{tabular*}{\textwidth}{@{}l@{\extracolsep{\fill}}ll@{}}
adjoin & maphash & reduce \\
assoc & mapl & remove \\
assoc-if & maplist & remove-duplicates \\
assoc-if-not & member & remove-if \\
count & member-if & remove-if-not \\
count-if & member-if-not & search \\
count-if-not & merge & set-difference \\
delete & mismatch & set-exclusive-or \\
delete-duplicates & nintersection & some \\
delete-if & notany & sort \\
delete-if-not & notevery & stable-sort \\
do-all-symbols & nset-difference & sublis \\
do-external-symbols & nset-exclusive-or & subsetp \\
do-symbols & nsublis & subst \\
dolist & nsubst & subst-if \\
eval & nsubst-if & subst-if-not \\
every & nsubst-if-not & substitute \\
find & nsubstitute & substitute-if \\
find-if & nsubstitute-if & substitute-if-not \\
find-if-not & nsubstitute-if-not & tree-equal \\
intersection & nunion & union \\
{\rm certain} loop {\rm clauses} & position & with-hash-table-iterator \\
map & position-if & with-input-from-string \\
mapc & position-if-not & with-output-to-string \\
mapcan & rassoc & with-package-iterator \\
mapcar & rassoc-if \\
mapcon & rassoc-if-not
\end{tabular*}
\endgroup
\end{new}
\end{table}


\section{Multiple Values}
\indexterm{multiple values}

Ordinarily the result of calling a Lisp function is a single Lisp object.
Sometimes, however, it is convenient for a function to compute several
objects and return them.
Common Lisp provides a mechanism for handling multiple values directly.
This mechanism is cleaner and more efficient than the usual tricks
involving returning a list of results or stashing results in global
variables.

\subsection{Constructs for Handling Multiple Values}

Normally multiple values are not used.  Special forms are
required both to {\it produce} multiple values and to {\it receive} them.
If the caller of a function does not request multiple values,
but the called function produces multiple values, then the first
value is given to the caller and all others are discarded;
if the called function produces zero values, then the caller gets {\false}
as a value.

The primary primitive for producing multiple values is \cd{values},
which takes any number of arguments and returns that many values.  If the
last form in the body of a function is a \cd{values} with three arguments,
then a call to that function will return three values.  Other special
forms also produce multiple values, but they can be described in terms of
\cd{values}.  Some built-in Common Lisp functions, such as \cd{floor}, return
multiple values; those that do are so documented.

The special forms and macros for receiving multiple values are as follows:
\begin{lisp}
multiple-value-list \\
multiple-value-call \\
multiple-value-prog1 \\
multiple-value-bind \\
multiple-value-setq
\end{lisp}
These specify a form to evaluate and an indication of where to put
the values returned by that form.

\begin{defun}[Function]
values &rest args

All of the arguments are returned, in order, as values.
For example:
\begin{lisp}
(defun polar (x y) \\
~~(values (sqrt (+ (* x x) (* y y))) (atan y x))) \\
 \\
(multiple-value-bind (r theta) (polar 3.0 4.0) \\
~~(vector r theta)) \\
~~~\EV\ \#(5.0 0.9272952)
\end{lisp}

The expression \cd{(values)} returns zero values.  This is the standard idiom
for returning no values from a function.

Sometimes it is desirable to indicate explicitly that a function will return
exactly one value.  For example, the function
\begin{lisp}
(defun foo (x y) \\
~~(floor (+ x y) y))
\end{lisp}
will return two values because \cd{floor} returns
two values.  It may be that the second value makes no sense,
or that for efficiency reasons it is desired not to compute the
second value.  The \cd{values} function is the standard idiom
for indicating that only one value is to be returned,
as shown in the following example.
\begin{lisp}
(defun foo (x y) \\
~~(values (floor (+ x y) y)))
\end{lisp}
This works because \cd{values} returns exactly {\it one} value for each of
its argument forms; as for any function call,
if any argument form to \cd{values} produces more than one value, all but the
first are discarded.

There is absolutely no way in Common Lisp for a caller to distinguish between
returning a single value in the ordinary manner and returning
exactly one ``multiple value.''  For example, the values returned
by the expressions \cd{(+~1~2)} and \cd{(values (+~1~2))} are identical
in every respect: the single value \cd{3}.
\end{defun}

\begin{defun}[Constant]
multiple-values-limit

The value of \cd{multiple-values-limit} is a positive integer that is
the upper exclusive bound on the number of values that may
be returned from a function.  This bound depends on the implementation
but will not be smaller than 20.
(Implementors are encouraged to make this limit as large as practicable
without sacrificing performance.)
See \cd{lambda-parameters-limit} and \cd{call-arguments-limit}.
\end{defun}

\begin{defun}[Function]
values-list list

All of the elements of {\it list} are returned as multiple values.
For example:
\begin{lisp}
(values-list (list a b c)) \EQ\ (values a b c)
\end{lisp}
In general,
\begin{lisp}
(values-list {\it list}) \EQ\ (apply \#'values {\it list})
\end{lisp}
but \cd{values-list} may be clearer or more efficient.
\end{defun}

\begin{defmac}
multiple-value-list form

\cd{multiple-value-list} evaluates {\it form} and returns a list of
the multiple values it returned.
For example:
\begin{lisp}
(multiple-value-list (floor -3 4)) \EV\ (-1 1)
\end{lisp}
\cd{multiple-value-list} and \cd{values-list} are therefore inverses
of each other.
\end{defmac}

\begin{defspec}
multiple-value-call function {\,form}*

\cd{multiple-value-call} first evaluates {\it function} to obtain a function
and then evaluates all of the {\it form\/}s.  All the values
of the {\it form\/}s are gathered together (not just one value from each)
and are all given as arguments to the function.  The result of \cd{multiple-value-call}
is whatever is returned by the function.
For example:
\begin{lisp}
(+ (floor 5 3) (floor 19 4)) \\
~~~\EQ\ (+ 1 4) \EV\ 5 \\
(multiple-value-call \#'+ (floor 5 3) (floor 19 4)) \\
~~~\EQ\ (+ 1 2 4 3) \EV\ 10 \\
(multiple-value-list {\it form}) \EQ\ (multiple-value-call \#'list {\it form})
\end{lisp}
\end{defspec}

\begin{defspec}
multiple-value-prog1 form {\,form}*

\cd{multiple-value-prog1} evaluates the first {\it form} and saves all the values
produced by that form.  It then evaluates the other {\it form}s
from left to right, discarding their values.  The values produced
by the first {\it form} are returned by \cd{multiple-value-prog1}.  See \cd{prog1},
which always returns a single value.
\end{defspec}

\begin{defmac}
multiple-value-bind ({var}*) values-form
                    {declaration}* {\,form}*

The {\it values-form} is evaluated, and each of the variables {\it var} is
bound to the respective value returned by that form.  If there are more
variables than values returned, extra values of {\false} are given to the
remaining variables.  If there are more values than variables, the excess
values are simply discarded.  The variables are bound to the values over
the execution of the forms, which make up an implicit \cd{progn}.
For example:
\begin{lisp}
(multiple-value-bind (x) (floor 5 3) (list x)) \EV\ (1) \\
(multiple-value-bind (x y) (floor 5 3) (list x y)) \EV\ (1 2) \\
(multiple-value-bind (x y z) (floor 5 3) (list x y z)) \\
~~~\EV\ (1 2 {\false})
\end{lisp}
\end{defmac}

\begin{defmac}
multiple-value-setq variables form

The {\it variables} must be a list of variables.  The {\it form} is
evaluated, and the variables are {\it set} (not bound) to the values
returned by that form.  If there are more variables than values returned,
extra values of {\false} are assigned to the remaining variables.  If there
are more values than variables, the excess values are simply discarded.

\beforenoterule
\begin{incompatibility}
In Lisp Machine Lisp this is called \cd{multiple-value}.
The added clarity of the name \cd{multiple-value-setq} in Common Lisp was deemed
worth the incompatibility with Lisp Machine Lisp.
\end{incompatibility}
\afternoterule

\newpage%manual

\cd{multiple-value-setq} always returns a single value, which is the first
value returned by {\it form}, or {\false} if {\it form} produces zero values.

\begin{newer}
X3J13 voted in March 1989
\issue{SYMBOL-MACROLET-SEMANTICS} to specify that if any {\it var}
refers not to an ordinary variable but to a binding made by
\cd{symbol-macrolet}, then that {\it var} is handled as
if \cd{setq} were used to assign the appropriate value to it.
\end{newer}
\end{defmac}


\begin{new}
\begin{defmac}*
nth-value n form

X3J13 voted in January 1989
\issue{NTH-VALUE}
to add a new macro named \cd{nth-value}.
The argument forms {\it n} and {\it form} are both evaluated.
The value of {\it n} must be a non-negative integer,
and the {\it form} may produce any number of values.
The integer {\it n} is used as a zero-based index into the
list of values.
Value {\it n} of the {\it form} is returned as the
single value of the \cd{nth-value} form; \cd{nil} is returned if the
{\it form} produces no more than {\it n} values.

As an example, \cd{mod} could be defined as
\begin{lisp}
(defun mod (number divisor) \\*
~~(nth-value 1 (floor number divisor)))
\end{lisp}
Value number 1 is the {\it second} value returned by \cd{floor},
the first value being value number 0.

One could define \cd{nth-value} simply as
\begin{lisp}
(defmacro nth-value (n form) \\*
~~{\Xbq}(nth ,n (multiple-value-list ,form)))
\end{lisp}
but the clever implementor will doubtless find an implementation
technique for \cd{nth-value} that avoids constructing an intermediate
list of all the values of the {\it form}.
\end{defmac}
\end{new}

\subsection{Rules Governing the Passing of Multiple Values}

It is often the case that the value
of a special form or macro call
is defined to be the value of one of its subforms.
For example, the
value of a \cd{cond} is the value of the last form in the selected clause.

In most such cases, if the subform produces multiple values, then the original
form will also produce all of those values.
This {\it passing back} of
multiple values of course has no effect unless eventually one of the
special forms for receiving multiple values is reached.

To be explicit, multiple values can result from a special form
under precisely these circumstances:
\goodbreak
\begin{flushdesc}
\item[{\it Evaluation and application}]\leavevmode
\begin{itemize}
\item
\cd{eval} returns multiple values if the form given it to
evaluate produces multiple values.

\item
\cd{apply}, \cd{funcall}, and \cd{multiple-value-call}
pass back multiple values from the function applied or called.
\end{itemize}

\item[{\it Implicit \cd{progn} contexts}]\leavevmode
\begin{itemize}
\item
The special form \cd{progn}
passes back multiple values resulting from evaluation of the
last subform.  Other situations referred to as ``implicit \cd{progn},''
where several forms are evaluated and the results of all but the last form
are discarded, also pass back multiple values from the last form.
These situations include the body of a lambda-expression,
in particular those constructed by \cd{defun},
\cd{defmacro}, and \cd{deftype}.
Also included are bodies of the constructs
\cd{eval-when},
\cd{progv}, \cd{let},
\cd{let*}, \cd{when}, \cd{unless},
\cd{block},
\cd{multiple-value-bind}, and \cd{catch},
as well as clauses in such conditional
constructs as
\cd{case}, \cd{typecase},
\cd{ecase}, \cd{etypecase}, \cd{ccase}, and \cd{ctypecase}.
\end{itemize}
\end{flushdesc}

\begin{new}
X3J13 has voted to add many new constructs to the language that contain
implicit \cd{progn} contexts.  I won't attempt to list them all here.
Of particular interest, however, is \cd{locally}, which may be regarded
as simply a version of \cd{progn} that permits declarations before its
body.  This provides a useful building block for constructing macros
that permit declarations (but not documentation strings)
before their bodies and pass back any multiple values
produced by the last sub-form of a body.  (If a body can contain a documentation
string, most likely \cd{lambda} is the correct building block to use.)
\end{new}

\begin{flushdesc}
\item[{\it Conditional constructs}]\leavevmode
\begin{itemize}
\item
\cd{if} passes back multiple values from whichever subform is selected
(the {\it then} form or the {\it else} form).

\item
\cd{and} and \cd{or} pass back multiple values from the last subform
but not from subforms other than the last.

\item
\cd{cond} passes back multiple values from the last subform of
the implicit \cd{progn} of the selected clause.
If, however, the clause selected is a singleton clause,
then only a single value (the non-{\false} predicate value)
is returned.  This is true even if the singleton clause is
the last clause of the \cd{cond}.  It is {\it not} permitted to
treat a final clause \cd{(x)} as being the same as \cd{(t x)}
for this reason; the latter passes back multiple values from the form \cd{x}.
\end{itemize}

\item[{\it Returning from a block}]\leavevmode
\begin{itemize}
\item
The \cd{block} construct passes back multiple values from its last subform
when it exits normally.  If \cd{return-from} (or \cd{return}) is
used to terminate the \cd{block} prematurely, then \cd{return-from}
passes back multiple values from its subform as the values of the
terminated \cd{block}.  Other constructs that create implicit blocks,
such as
\cd{do}, \cd{dolist}, \cd{dotimes}, \cd{prog}, and
\cd{prog*}, also pass back multiple values specified by
\cd{return-from} (or \cd{return}).

\item
\cd{do} passes back multiple values from
the last form of the exit clause, exactly as if the exit clause
were a \cd{cond} clause.  Similarly, \cd{dolist} and \cd{dotimes}
pass back multiple values from the {\it resultform} if that is executed.
These situations are all examples of implicit uses of \cd{return-from}.
\end{itemize}

\item[{\it Throwing out of a catch}]\leavevmode
\begin{itemize}
\item
The \cd{catch} construct returns multiple values if
the result form in a \cd{throw} exiting from
such a catch produces multiple values.
\end{itemize}

\item[{\it Miscellaneous situations}]\leavevmode
\begin{itemize}
\item
\cd{multiple-value-prog1} passes back multiple values from its first
subform.  However, \cd{prog1} always returns a single value.

\item
\cd{unwind-protect} returns multiple values if the form it protects
returns multiple values.

\item
\cd{the} returns multiple values if the form it contains returns
multiple values.
\end{itemize}
\end{flushdesc}

Among special forms that {\it never} pass back multiple values are
\cd{prog1},
\cd{prog2}, \cd{setq}, and \cd{multiple-value-setq}.
The conventional way to force only one value to be returned from a form \cd{x}
is to write \cd{(values x)}.

The most important rule about multiple values is:
{\bf No matter how many values a form produces,
if the form is an argument form in a function call,
then exactly one value (the first one) is used.}

For example, if you write \cd{(cons (floor x))}, then \cd{cons} will always
receive {\it exactly} one argument (which is of course an error),
even though \cd{floor} returns two values.  To pass both values from \cd{floor}
to \cd{cons}, one must write something like
\cd{(multiple-value-call \#'cons (floor x))}.
In an ordinary function call,
each argument form produces exactly {\it one} argument;  if such a form
returns zero values, {\false} is used for the argument, and if more than one
value, all but the first are discarded.
Similarly, conditional constructs such as \cd{if} that test the value of a form
will use exactly one value, the first one, from that form and discard the rest;
such constructs will use {\false} as the test value if zero values are returned.

\section{Dynamic Non-Local Exits}
\label{CATCH-THROW-SECTION}
\indexterm{non-local exit}
\indexterm{dynamic exit}
\indexterm{catch}
\indexterm{throw}

Common Lisp provides a facility for exiting from a complex process
in a non-local, dynamically scoped manner.  There are two classes of
special forms for this purpose, called {\it catch} forms and {\it throw}
forms, or simply {\it catches} and {\it throws}.  A catch form evaluates some
subforms in such a way that, if a throw form is executed during such
evaluation, the evaluation is aborted at that point and the catch form
immediately returns a value specified by the throw.  Unlike \cd{block}
and \cd{return} (section~\ref{BLOCK-RETURN-SECTION}),
which allow for exiting a \cd{block} form from any
point lexically within the body of the \cd{block}, the catch/throw
mechanism works even if the throw form is not textually within the body
of the catch form.  The throw need only occur within the extent (time
span) of the evaluation of the body of the catch.  This is analogous to
the distinction between dynamically bound (special) variables and
lexically bound (local) variables.

\begin{defspec}
catch tag {\,form}*

The \cd{catch} special form serves as a target for transfer
of control by \cd{throw}.
The form {\it tag} is evaluated first to produce an object
that names the catch; it may be any Lisp object.
A catcher is then established with the object as the tag.
The {\it form\/}s are evaluated as an implicit \cd{progn},
and the results of the last form are returned,
except that if during the evaluation of the {\it form\/}s
a throw should be executed such that the tag
of the throw matches (is \cd{eq} to) the tag of the \cd{catch}
and the catcher is the most recent outstanding catcher with that tag,
then the evaluation of the {\it form\/}s is aborted and the results
specified by the throw
are immediately returned from the \cd{catch} expression.
The catcher established by the \cd{catch} expression is disestablished
just before the results are returned.

The tag is used to match throws with catches.
\cd{(catch 'foo {\it form})} will catch a \cd{(throw 'foo {\it form})} but
not a \cd{(throw 'bar {\it form})}.  It is an error if \cd{throw} is done
when there is no suitable \cd{catch} ready to catch it.

Catch tags are compared using \cd{eq},
not \cd{eql}; therefore numbers and characters
should not be used as catch tags.

\beforenoterule
\begin{incompatibility}
The name \cd{catch} comes from MacLisp,
but the syntax of \cd{catch} in Common Lisp is different.
The MacLisp syntax was \cd{(catch {\it form} {\it tag})},
where the {\it tag} was not evaluated.
\end{incompatibility}
\afternoterule
\end{defspec}

\indexterm{unwind protection}
\indexterm{cleanup handler}
\begin{defspec}
unwind-protect protected-form {cleanup-form}*

Sometimes it is necessary to evaluate a form and make sure that
certain side effects take place after the form is evaluated;
a typical example is
\begin{lisp}
(progn (start-motor) \\*
~~~~~~~(drill-hole) \\*
~~~~~~~(stop-motor))
\end{lisp}
The non-local exit facility of Common Lisp creates a situation in which
the above code won't work, however: if \cd{drill-hole} should
do a throw to a catch that is outside of the \cd{progn}
form (perhaps because the drill bit broke),
then \cd{(stop-motor)} will never be evaluated
(and the motor will presumably be left running).
This is particularly likely if \cd{drill-hole} causes a Lisp error
and the user tells the error-handler to give up and abort
the computation.
(A possibly more practical example might be
\begin{lisp}
(prog2 (open-a-file) \\*
~~~~~~~(process-file) \\*
~~~~~~~(close-the-file))
\end{lisp}
where it is desired always to close the file when the computation
is terminated for whatever reason.  This case is so important
that Common Lisp provides the special form \cd{with-open-file} for
this purpose.)

In order to allow the example hole-drilling program to work, it can
be rewritten using \cd{unwind-protect} as follows:
\begin{lisp}
;; Stop the motor no matter what (even if it failed to start). \\*
\\*
(unwind-protect \\*
~~(progn (start-motor) \\*
~~~~~~~~~(drill-hole)) \\*
~~(stop-motor))
\end{lisp}
If \cd{drill-hole} does a throw that attempts to quit out of the
\cd{unwind-protect}, then \cd{(stop-motor)} will be executed.

This example assumes that it is correct to call \cd{stop-motor}
even if the motor has not yet been started.  Remember that
an error or interrupt may cause an exit even before any initialization
forms have been executed.  Any state restoration code
should operate correctly no matter where in the protected code an
exit occurred.  For example, the following code
is not correct:
\begin{lisp}
(unwind-protect \\*
~~(progn (incf *access-count*) \\*
~~~~~~~~~(perform-access)) \\*
~~(decf *access-count*))
\end{lisp}
If an exit occurs before completion of the \cd{incf} operation
the \cd{decf} operation will be executed anyway, resulting in an
incorrect value for \cd{*access-count*}.
The correct way to code this is as follows:
\begin{lisp}
(let ((old-count *access-count*)) \\
~~(unwind-protect \\
~~~~(progn (incf *access-count*) \\
~~~~~~~~~~~(perform-access)) \\
~~~~(setq *access-count* old-count)))
\end{lisp}

As a general rule, \cd{unwind-protect} guarantees to execute
the {\it cleanup-form\/}s before exiting, whether it terminates
normally or is aborted by a throw of some kind.
(If, however, an exit occurs during execution of the {\it cleanup-form\/}s,
no special action is taken.  The {\it cleanup-form\/}s of an \cd{unwind-protect}
are not protected by that \cd{unwind-protect}, though they may be
protected if that \cd{unwind-protect} occurs within the protected
form of another \cd{unwind-protect}.)
\cd{unwind-protect} returns whatever results from evaluation of
the {\it protected-form} and discards all the results
from the {\it cleanup-form\/}s.

It should be emphasized that \cd{unwind-protect} protects against
{\it all} attempts to exit from the protected form,
including not only ``dynamic exit'' facilities such as \cd{throw}
but also ``lexical exit'' facilities such as \cd{go} and
\cd{return-from}.  Consider this situation:
\begin{lisp}
(tagbody \\
~~(let ((x 3)) \\
~~~~(unwind-protect \\
~~~~~~(if (numberp x) (go out)) \\
~~~~~~(print x))) \\
~out \\
~~...)
\end{lisp}
When the \cd{go} is executed, the call to \cd{print} is executed first,
and then the transfer of control to the tag \cd{out} is completed.

\begin{newer}
X3J13 voted in March 1989 \issue{EXIT-EXTENT} to clarify the interaction
of \cd{unwind-protect} with constructs that perform exits.

Let an {\it exit} be a point out of which control can be transferred.
For a \cd{throw} the exit is the matching \cd{catch}; for
a \cd{return-from} the exit is the corresponding \cd{block}.
For a \cd{go} the exit is the statement within the \cd{tagbody} (the one to which
the target tag belongs) which is being executed at the time the \cd{go} is performed.

The extent of an exit is dynamic; it is not indefinite. The extent
of an exit begins when the corresponding form (\cd{catch}, \cd{block}, or \cd{tagbody}
statement) is entered.  When the extent of an exit has ended, it is no
longer legal to return from it.

Note that the extent of an exit is not the same thing as the scope or extent of the
designator by which the exit is identified. For example, a \cd{block}
name has lexical scope but the extent of its exit is dynamic.  The
extent of a \cd{catch} tag could differ from the extent of the exit
associated with the \cd{catch} (which is exactly what is at issue here).
The difference matters when there are transfers
of control from the cleanup clauses of an \cd{unwind-protect}.

When a transfer of control out of an exit is initiated by \cd{throw},
\cd{return-from}, or \cd{go},
a variety of events occur before the transfer of control is complete:
\begin{itemize}
\item The cleanup clauses of any intervening \cd{unwind-protect} clauses
    are evaluated.
\item Intervening dynamic bindings of special variables and catch tags
    are undone.
\item Intervening exits are {\it abandoned}, that is, their extent ends and it
    is no longer legal to attempt to transfer control from them.
\item The extent of the exit being invoked ends.
\item Control is finally passed to the target.
\end{itemize}
The first edition left the order of these events in some doubt.
The implementation note for \cd{throw} hinted that the first two processes
are interwoven, but it was unclear whether it is permissible
for an implementation to abandon all 
intervening exits before processing any intervening \cd{unwind-protect}
cleanup clauses.

The clarification adopted by X3J13 is as follows.
Intervening exits are abandoned as soon as the transfer of control is initiated;
in the case of a \cd{throw}, this occurs at the beginning of the ``second pass''
mentioned in the implementation note.  It is an error to
attempt a transfer of control to an exit whose dynamic extent has
ended.

Next the evaluation of \cd{unwind-protect} cleanup clauses and the
undoing of dynamic bindings and \cd{catch} tags are performed together,
in the order corresponding to the reverse of the order
in which they were established.
The effect of this is that the cleanup clauses of an \cd{unwind-protect}
will see the same dynamic bindings of variables and \cd{catch} tags as were
visible when the \cd{unwind-protect} was entered.  (However, some of those
\cd{catch} tags may not be useable because they correspond to abandoned
exit points.)

Finally  control is transferred to
the originally invoked exit and simultaneously that exit is abandoned.

The effect of this specification is that once a program has attempted
to transfer control to a particular exit, an \cd{unwind-protect} cleanup
form cannot
step in and decide to transfer control to a more recent (nested) exit,
blithely forgetting the original exit request.  However, a cleanup form
may restate the request to transfer to the same exit that started
the cleanup process.

Here is an example based on a nautical metaphor.  The function \cd{gently}
moves an oar in the water with low force, but if an oar gets stuck, the caller
will catch a crab.  The function \cd{row}
takes a boat, an oar-stroking function,
a stream, and a count; an oar is constructed for the boat and stream
and the oar-stroking function is called \cd{:count} times.
The function \cd{life} rows a particular boat.
Merriment follows, except that if the oarsman is winded he must stop
to catch his breath.
\begin{lisp}
(defun gently (oar) \\*
~~(stroke oar :force 0.5) \\*
~~(when (stuck oar) \\*
~~~~(throw 'crab nil))) \\
\\
(defun row (boat stroke-fn stream \&key count) \\*
~~(let ((oar (make-oar boat stream))) \\*
~~~~(loop repeat count do (funcall stroke-fn oar)))) \\
\\
(defun life () \\*
~~(catch 'crab \\*
~~~~(catch 'breath \\*
~~~~~~(unwind-protect \\*
~~~~~~~~(row *your-boat* \#'gently *query-io* :count 3)) \\*
~~~~~~~~(when (winded) (throw 'breath nil))) \\*
~~~~~~(loop repeat 4 (set-mode :merry)) \\*
~~~~~~(dream))))
\end{lisp}
Suppose that the oar gets stuck, causing \cd{gently} to call \cd{throw}
with the tag \cd{crab}.
The program is then committed to exiting from the outer \cd{catch} (the one
with the tag \cd{crab}).  As control breaks out of the \cd{unwind-protect} form,
the \cd{winded} test is executed.  Suppose it is true; then another call to \cd{throw}
occurs, this time with the tag \cd{breath}.  The inner \cd{catch} (the one with
the tag \cd{breath}) has been abandoned as a result of the first
\cd{throw} operation (still in progress).  The clarification voted by X3J13
specifies that the program is in error for attempting to transfer control
to an abandoned exit point.  To put it in terms of the example: once you have
begun to catch
a crab, you cannot rely on being able to catch your breath.

Implementations may support longer extents for exits than is
required by this specification,
but portable programs may not rely on such extended extents.

(This specification is somewhat controversial.  An alternative proposal was
that the abandoning of exits should be lumped in with
the evaluation of \cd{unwind-protect} cleanup clauses and the
undoing of dynamic bindings and \cd{catch} tags, performing all
in reverse order of establishment.  X3J13 agreed that this approach is
theoretically cleaner and more elegant but also more stringent
and of little additional practical use.  There was some concern that
a more stringent specification might be a great added burden to some
implementors and would achieve only a small gain for users.)
\end{newer}
\end{defspec}

\begin{defspec}
throw tag result

The \cd{throw} special form transfers control to a matching
\cd{catch} construct.
The {\it tag} is evaluated first to produce an object
called the throw tag; then the {\it result} form is evaluated,
and its results are saved (if the {\it result} form produces
multiple values, then {\it all} the values are saved).
The most recent outstanding catch whose tag matches the throw tag
is exited; the saved results are returned as the value(s) of the catch.
A \cd{catch} matches only if the catch tag is \cd{eq} to the throw tag.

In the process, dynamic variable
bindings are undone back to the point of the catch, and any intervening
\cd{unwind-protect} cleanup code is executed.
The {\it result} form is evaluated before the unwinding process commences,
and whatever results it produces are returned from the catch.

If there is no outstanding catcher whose tag matches the throw tag,
no unwinding of the stack is performed, and an error is signalled.
When the error is signalled, the outstanding catchers and the dynamic
variable bindings are those in force at the point of the throw.

\beforenoterule
\begin{implementation}
These requirements imply that throwing should typically
make two passes over the control stack.  In the first pass it simply
searches for a matching catch.  In this search every \cd{catch}
must be considered, but every
\cd{unwind-protect} should be ignored.  On the second pass the stack
is actually unwound, one frame at a time, undoing dynamic bindings
and outstanding \cd{unwind-protect} constructs in reverse order of creation
until the matching catch is reached.
\end{implementation}
\betweennoterule
\begin{incompatibility}
The name \cd{throw} comes from MacLisp,
but the syntax of \cd{throw} in Common Lisp is different.
The MacLisp syntax was \cd{(throw {\it form} {\it tag})},
where the {\it tag} was not evaluated.
\end{incompatibility}
\afternoterule
\end{defspec}
----------------------------------------------------------------